Logo
All Random Solved Random Open
SOLVED
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$?
This is true, as shown by Rödl [Ro77].

See [108] for a more general question.

Additional thanks to: Sophie Spirkl