2012/12/30 by Allan Lo, Lo, Allan
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1212.6735
Minor revision. Accepted for publication in SIAM Journal Discrete Mathematics
arxiv created 2013/12/10 · arxiv updated 2013/12/11
Let G be an edge-coloured graph. The minimum colour degree δc(G) of G is the largest integer k such that, for every vertex v, there are at least k distinct colours on edges incident to v. We say that G is properly coloured if no two adjacent edges have the same colour. In this paper, we show that every edge-coloured graph G with δc(G) ≥ 2|G| / 3 contains a properly coloured 2-factor. Furthermore, we show that for any ε > 0 there exists an integer n0 such that every edge-coloured graph G with |G| = n ≥ n0 and δc(G) ≥ ( 2/3 + ε ) n contains a properly coloured cycle of length ℓ for every 3 ≤ ℓ ≤ n. This result is best possible in the sense that the statement is false for δc(G) < 2n / 3 .