Must a triangle-free graph of infinite chromatic number induce every tree? (Erdős #738)
Statement
If $G$ has infinite chromatic number and is triangle-free (contains no $K_3$), must $G$ contain every finite tree as an induced subgraph?
Acceptance. FULLY RESOLVES: a complete proof that every triangle-free graph with infinite chromatic number contains every finite tree as an induced subgraph; or a counterexample — an explicit triangle-free graph of infinite chromatic number together with a specific finite tree $T$ and a proof that $T$ does not occur in it as an induced subgraph. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: a proof for a class of trees strictly extending the radius-2 frontier stated in the background (e.g. all radius-3 trees, or all spiders/subdivided stars not covered by known results), clearly identifying the new class; a proof under a strengthened hypothesis (girth $>g$ for some fixed $g$) covering all trees; or a proof that a specific standard family of triangle-free graphs with unbounded chromatic number (e.g. shift graphs) induces every finite tree. Deliver the proof file (and for a counterexample, the construction with the non-embedding proof).
Background
A conjecture of Gyárfás, recorded by Erdős in [Er81]; listed as open on erdosproblems.com/738 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). It is the infinite-chromatic, triangle-free cousin of the celebrated Gyárfás–Sumner conjecture (graphs excluding a fixed tree $T$ as an induced subgraph and a fixed clique $K_t$ have bounded chromatic number); Gyárfás–Sumner, if true, implies this conjecture. The known frontier follows from chi-boundedness results for restricted tree classes: Gyárfás (1987) proved that $P_k$-free graphs are chi-bounded, so any graph of infinite chromatic number contains every path as an induced subgraph; Kierstead and Penrice (1994) proved the Gyárfás–Sumner conjecture for trees of radius 2, so triangle-free graphs of infinite chromatic number contain every radius-2 tree as an induced subgraph; Scott (1997) proved a topological analogue giving induced subdivisions of every tree in graphs of large chromatic number with bounded clique number. The general case — arbitrary trees, even assuming triangle-freeness — remains open. The attacker's tool: proof-shaped structural graph theory (chi-boundedness machinery in the Kierstead–Penrice/Scott–Seymour tradition, or a counterexample analysis of the standard triangle-free high-chromatic families such as shift graphs, Kneser graphs, and Zykov/Mycielski towers, which serve as natural test beds for candidate counterexample trees); no finite computation can decide the conjecture.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #738 (T. F. Bloom) | website |
| REF-02 | Gyárfás–Sumner conjecture (finite-chromatic analogue) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.