Graphs of arbitrarily high girth and chromatic number
ID: graphs-of-arbitrarily-high-girth-and-chromatic-number
For every , there is a finite graph with no cycle of length at most and with chromatic number at least . 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.
New to topics? Read the docs here!