Does huge chromatic number force an odd cycle spanning a subgraph of chromatic number k? (Erdős #640)
Statement
Let $k\geq 3$. Does there exist some $f(k)$ such that every graph $G$ with chromatic number $\geq f(k)$ must contain some odd cycle whose vertices span a subgraph of chromatic number $\geq k$?
Acceptance. FULLY RESOLVES: a complete proof that $f(k)$ exists for every $k\geq 3$ (explicit bounds welcome but not required), or a disproof — an explicit infinite family of graphs with chromatic number tending to infinity together with a proof that, for some fixed $k\geq 4$, every odd cycle in each family member spans a subgraph of chromatic number $<k$. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: a proof of the first open case $k=4$; a proof of the statement for graphs of bounded clique number or another infinite structured class; a new reduction or equivalence strictly extending Steiner's odd-cycle/path equivalence stated in the background, with proof; or verified computational evidence in the counterexample direction — a concrete graph family with certified chromatic numbers (graph files plus colouring/non-colourability certificates) in which all odd cycles are shown to span only low-chromatic subgraphs, accompanied by the verification code. Deliver the proof file, or the construction plus certificates and code.
Background
A problem of Erdős and Hajnal, recorded by Erdős in [Er97d]; listed as open on erdosproblems.com/640 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). The case $k=3$ is trivial with $f(3)=4$: any non-bipartite graph contains an odd cycle, and every odd cycle has chromatic number 3. The first open case is $k=4$: must graphs of sufficiently large chromatic number contain an odd cycle whose vertex set spans a 4-chromatic subgraph? Raphael Steiner observed (in the site's comments, incorporated into Bloom's remarks) that the problem is equivalent to the variant in which 'odd cycle' is replaced by 'path'. No nontrivial bounds or partial cases appear in the site's commentary beyond these observations, so the frontier is essentially the trivial $k=3$ case plus Steiner's equivalence. The attacker's tool: structural graph theory — BFS-layering and level-set decompositions of the kind used in chi-boundedness arguments, or a counterexample family of graphs with unbounded chromatic number (shift graphs, Kneser graphs, Zykov/Mycielski towers) in which every odd cycle spans a subgraph of chromatic number at most 3; small-scale computation can stress-test such candidate families before attempting the infinite-family proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #640 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.