Note edge-colourings of Kn,n with no long two-coloured cycles |
| |
Authors: | Peter Dukes Alan C. H. Ling |
| |
Affiliation: | (1) Department of Mathematics and Statistics, University of Victoria, Victoria, BC, V8W 3P4, Canada;(2) Department of Computer Science, University of Vermont, Burlington, Vermont 05405, USA |
| |
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. |
| |
Keywords: | KeywordHeading" >Mathematics Subject Classification (2000) 05C15 05B25 |
本文献已被 SpringerLink 等数据库收录! |
|