Status
On this page
Status
Topics
Status
On this page
Status
Topics
For every and is there some finite such that every graph of chromatic number contains a subgraph of girth and chromatic number ?
Source: erdosproblems.com/108
An accepted solution exists. The statement is false.
Open on the site: the label is OPEN and the page was last edited 23 January 2026; on 27 September 2026 the curator posted the Conjectures.io claim below on the site's proof-claims forum without endorsing it. The derived standing rests on the accepted claim page of Kohlmeyer and Kruer's Lean counterexample family, published under the handle JenW1N and certified by Conjectures.io in September 2026: for every a finite graph of chromatic number at least all of whose subgraphs of girth at least are -colorable, so no finite exists. That certification is documented independent acceptance by the bounty site, with no refereed publication and no formalization built here. The expository note of Nguyen and Walczak (30 September 2026) explains the construction and sharpens the bound to , which refutes every with ; it is a pending claim. The case is Rödl's theorem, an accepted partial claim (triangle-free subgraphs of large chromatic number; it is the whole of Problem 923), for which Steiner's preprint (August 2026) gives a second proof with a single-exponential bound in place of Rödl's tower, a pending partial claim; the cases with hold for the elementary reasons given below. The infinitary version is Problem 740.