Problem Statement
Let $f_r(n)$ be maximal such that, if a graph $G$ has the property that every subgraph $H$ on $m$ vertices is the union of a graph with chromatic number $r$ and a graph with $\leq f_r(m)$ edges, then $G$ has chromatic number $\leq r+1$.
Is it true that $f_2(n) \gg n$? More generally, is $f_r(n)\gg_r n$?
Is it true that $f_2(n) \gg n$? More generally, is $f_r(n)\gg_r n$?
Categories:
Graph Theory Chromatic Number
Progress
A conjecture of Erdős, Hajnal, and Szemerédi. This seems to be closely related to, but distinct from, [744].Tang notes in the comments that a construction of Rödl [Ro82] disproves the first question, so that $f_2(n)\not\gg n$.
Source: erdosproblems.com/1092 | Last verified: January 19, 2026