Originator(s): Michael Albertson, Lily Chan, and Ruth Haas
Question: It is true that every n-vertex graph with odd girth at least 2k+1 and minimum degree greater than 3n/(4k) is C2k+1-colorable?
Comments/Partial results: The degree threshold is sharp, as shown by the Möbius ladder of order 4k; this graph consists of a 4k-cycle plus all chords joining opposite vertices on the cycle. The graph has odd girth 2k+1 and minimum degree 3n/(4k), but it has no C2k+1-coloring.
For n-vertex graphs with odd girth at least 2k+1, Albertson, Chan, and Haas [ACH] proved that minimum degree greater than n/(k+1) suffices for the existence of C2k+1-colorings. Lai and Yu [LY] reduced the degree threshold in the general case to 2n/(2k+3). The case k=2 was completely solved earlier by Häggkvist [H].
References:
[ACH] Albertson, M. O.; Chan, L.; Haas, R.
Independence and graph homomorphisms.
J. Graph Theory 17 (1993), no. 5, 581--588.
[H] Häggkvist, R. Odd cycles of specified length in nonbipartite graphs.
Graph theory (Cambridge, 1981), pp. 89--99, North-Holland Math. Stud., 62,
North-Holland, Amsterdam-New York, 1982.
[LY] Lai, H.-J.; Yu, G.
Graphic Homomorphism into an odd cycle, to appear.