Girth (graph Theory) - Girth and Graph Coloring

Girth and Graph Coloring

For any positive integers g and χ, there exists a graph with girth at least g and chromatic number at least χ; for instance, the Grötzsch graph is triangle-free and has chromatic number 4, and repeating the Mycielskian construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number. Paul Erdős was the first to prove the general result, using the probabilistic method. More precisely, he showed that a random graph on n vertices, formed by choosing independently whether to include each edge with probability n(1 − g)/g, has, with probability tending to 1 as n goes to infinity, at most n/2 cycles of length g or less, but has no independent set of size n/2k. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than g, in which each color class of a coloring must be small and which therefore requires at least k colors in any coloring.