Graphs of arbitrarily high girth and chromatic number
= Graphs of arbitrarily high girth and chromatic number
For every $g,k\geq3$, there is a finite graph with no cycle of length at most $g$ and with chromatic number at least $k$. A probabilistic proof samples a sparse binomial random graph, observes that it has few short cycles and no large independent set, and deletes one vertex from every short cycle.