Note edge-colourings of K n,n with no long two-coloured cycles.

Autor:	Peter Dukes, Alan Ling
Předmět:	GRAPH coloring ALGEBRAIC cycles LOGARITHMIC functions STATISTICS GRAPH theory
Zdroj:	Combinatorica; May2008, Vol. 28 Issue 3, p373-378, 6p
Abstrakt:	Abstract  Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K n,n with n colours having all two-coloured cycles of length ≤ 2q 2, for integers n in a set of density 1 − 3/(q − 1). One consequence is that L(n, K n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n − 4. [ABSTRACT FROM AUTHOR]
Databáze:	Complementary Index
Externí odkaz:	Zobrazit plný text záznamu Full text from SpringerLink