Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be an infinite cardinal and be a graph with chromatic number . Let . Must contain a subgraph of chromatic number which does not contain any odd cycle of length ?
Source: erdosproblems.com/740
A full solution has been claimed but not yet accepted. The statement is false.
Open on erdosproblems.com (label OPEN, accessed 2026-10-07). The site's notes call it a question of Erdős and Hajnal, record Rödl's theorem for and , and say that Erdős and Hajnal asked more generally for an such that chromatic number at least forces a subgraph of chromatic number with no odd cycle of length at most . The label does not record the refereed consistency result of Komjáth and Shelah (1988), under which the statement, as a question about every infinite cardinal, is not a theorem of ZFC; that result is one side of an independence result and leaves the problem open, as the label does. A refutation in ZFC alone, Johan Land's 2026 claim, is pending.
The site labels the problem OPEN and its commentary records no result beyond Rödl's. Komjáth and Shelah (J. Symbolic Logic 1988, refereed) proved it consistent with ZFC+CH that an -chromatic graph has only countably chromatic triangle-free subgraphs, so the affirmative answer, for every infinite cardinal, is not a theorem of ZFC; no model in which the answer is yes at is known, and no ZFC refutation is accepted (Land's 2026 claim is pending). On the related Problem 1175 the curator records Shelah's consistency result and keeps the label OPEN, so the site treats such a result as progress on an open problem, and this page does the same: the result is one side of an independence result and leaves the problem open.