**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 *C _{2k+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
*C _{2k+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
*C _{2k+1}*-colorings.
Lai and Yu [LY] reduced the degree threshold in the general case
to

**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.