Open Problem Garden

For a graph , we let denote the chromatic number, and the size of the largest clique. A hole is an induced cycle of length , so an odd hole is an induced cycle with length an odd number .

Thanks to the perfect graph theorem, we know that a graph is perfect ( for all induced subgraphs ) 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 , as in this case has no odd cycle, so . The special case when 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 there is a function so that every graph with no hole of size satisfies ). Graphs with no hole of size 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.