# chromatic number and girth

A famous theorem of P. Erdős^{1}^{1}See the very readable P. Erdős, and probability, Canad J. Math. 11 (1959), 34–38..

###### Theorem 1

For any natural numbers^{} $k$ and $g$, there exists a graph $G$ with chromatic number^{} $\chi \mathit{}\mathrm{(}G\mathrm{)}\mathrm{\ge}k$ and girth $\mathrm{girth}\mathit{}\mathrm{(}G\mathrm{)}\mathrm{\ge}g$.

Obviously, we can easily have graphs with high chromatic numbers. For instance, the complete graph^{} ${K}_{n}$ trivially has $\chi ({K}_{n})=n$; however $\mathrm{girth}({K}_{n})=3$ (for $n\ge 3$). And the cycle graph ${C}_{n}$ has $\mathrm{girth}({C}_{n})=n$, but

$$\chi ({C}_{n})=\{\begin{array}{cc}1\hfill & n=1\hfill \\ 2\hfill & n\text{even}\hfill \\ 3\hfill & \text{otherwise.}\hfill \end{array}$$ |

It seems intuitively plausible that a high chromatic number occurs because of short, “local” cycles in the graph; it is hard to envisage how a graph with no short cycles can still have high chromatic number.

Instead of envisaging, Erdős’ proof shows that, in some appropriately chosen probability space^{} on graphs with $n$ vertices, the probability of choosing a graph which does *not* have $\chi (G)\ge k$ and $\mathrm{girth}(G)\ge g$ tends to zero as $n$ grows. In particular, the desired graphs exist.

This seminal paper is probably the most famous application of the probabilistic method, and is regarded by some as the foundation of the method.^{2}^{2}However, as always, with the benefit of hindsight we can see that the probabilistic method had been used before, e.g. in various applications of Sard’s theorem. This does nothing to diminish from the importance of the clear statement of the tool. Today the probabilistic method is a standard tool for combinatorics. More constructive methods are often preferred, but are almost always much harder.

Title | chromatic number and girth |
---|---|

Canonical name | ChromaticNumberAndGirth |

Date of creation | 2013-03-22 12:46:03 |

Last modified on | 2013-03-22 12:46:03 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 7 |

Author | mathcam (2727) |

Entry type | Theorem |

Classification | msc 05C15 |

Classification | msc 05C38 |

Classification | msc 05C80 |

Related topic | Girth |

Related topic | ChromaticNumber |