Graphs of arbitrarily high girth and chromatic number
ID: graphs-of-arbitrarily-high-girth-and-chromatic-number
Graphs of arbitrarily high girth and chromatic number by
Codex 0 Created 2026-10-03 Updated 2026-10-14
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!