Bounding the chromatic number of graphs with no odd hole (Solved)

Importance: High ✭✭✭
Author(s): Gyarfas, Andras
Recomm. for undergrads: no
Posted by: mdevos
on: June 25th, 2007
Solved by: Alex Scott and Paul Seymour
Conjecture   There exists a fixed function $ f : {\mathbb N} \rightarrow {\mathbb N} $ so that $ \chi(G) \le f(\omega(G)) $ for every graph $ G $ with no odd hole.

For a graph $ G $, we let $ \chi(G) $ denote the chromatic number, and $ \omega(G) $ the size of the largest clique. A hole is an induced cycle of length $ \ge 4 $, so an odd hole is an induced cycle with length an odd number $ \ge 5 $.

Thanks to the perfect graph theorem, we know that a graph is perfect ($ \chi(H) = \omega(H) $ for all induced subgraphs $ H $) if and only if it has no odd hole, and no complement of an odd hole. Perfect graphs are a particularly pretty and well-behaved class, and the proof of the perfect graph theorem gives us a great deal of structural information about them. On the other hand, graphs with no odd hole are considerably more wild, so it appears unlikely that this conjecture could be established by way of a precise structure theorem.

The conjecture is trivial in the case when $ \omega(G) = 2 $, as in this case $ G $ has no odd cycle, so $ \chi(G) \le 2 $. The special case when $ \omega(G) = 3 $ was resolved by Robertson, Seymour, and Thomas who found a structural description of these graphs which implies that they are 4-colorable.

Gyarfas also posed a related conjecture that the same conclusion should hold true for the family of graphs which do not contain sufficiently large holes (more precisely, for every $ t $ there is a function $ f $ so that every graph $ G $ with no hole of size $ \ge t $ satisfies $ \chi(G) \le f(\omega(G)) $). Graphs with no hole of size $ \ge 4 $ are chordal and have clique number equal to their chromatic number, so they satisfy this conjecture. I (M. DeVos) believe it is open in all other cases.


*[G] A. Gyarfas, Problems from the world surrounding perfect graphs, [in Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985)]. Zastos. Mat. 19 (1987), no. 3-4, 413--441 MathSciNet

* indicates original appearance(s) of problem.