Albertson-Chan-Haas Problem (1993)

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.

Back to Index Page Link to Glossary