Problem 923

Is it true that, for every $k$ , there is some $f(k)$ such that if $G$ has chromatic number $\geq f(k)$ then $G$ contains a triangle-free subgraph with chromatic number $\geq k$ ?

Source: erdosproblems.com/923

Graph theory
Chromatic number

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN) on erdosproblems.com, whose commentary credits Rödl [Ro77] with the proof (claim page (Rödl, 1977)); the Lean qualifier refers to Parcly Taxel's Aristotle-assisted formalization of Rödl's theorem, posted in the problem's thread on 20 April 2026, which the formal-conjectures catalog later cited through Boris Alexeev's copy and which this corpus has not built. Problem 108 asks a more general question.

Problem 923

Status

Proof claims

Discussion