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.
Articles by others on the same topic
There are currently no matching articles.