Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is there some such that every graph with chromatic number has, for all large , a subgraph with chromatic number on at most vertices?
Source: erdosproblems.com/110
An accepted solution exists. The statement is false.
Disproved on the site (label DISPROVED; page last edited 1 October 2025). The site attributes the conjecture to Erdős, Hajnal and Szemerédi [EHS82], notes that it fails for graphs of chromatic number , recalls that de Bruijn and Erdős [dBEr51] guarantee a finite subgraph of every finite chromatic number inside any graph of infinite chromatic number, records Erdős's view in [Er95d] that the answer should be yes with an growing faster than every iterated exponential, and credits Shelah [KoSh05] (a paper joint with Komjáth) with the consistency of a negative answer and Lambie-Hanson [La20] with a counterexample in ZFC. The standing rests on Lambie-Hanson's theorem, accepted on its refereed publication and the curator's credit: for every function there is a graph of chromatic number in which, for every , every subgraph of chromatic number at least has at least vertices, so no works. The Komjáth–Shelah forcing result is an accepted partial claim: it showed the positive answer unprovable in ZFC without deciding the question.