Erdős Problem #1092 — 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…

The problem, posed by Erdős, Hajnal, and Szemerédi, asks whether a linear edge-error allowance forces global $(r+1)$-colourability. Rödl’s construction gives a negative answer: for every fixed $r\ge 2$, one has $f_r(n)=o(n)$, in the relevant strong sense.

Rödl’s 1982 disproof

Rödl’s graph $K^*(n,k)$ has chromatic number $k+2$, while every subgraph becomes bipartite after deleting at most $\epsilon |V(H)|$ edges. This contradicts any bound $f_2(n)\ge cn$ and, by joining with a clique of size $r-2$, yields $f_r(n)=o(n)$ for every fixed $r\ge 2$. The source is Rödl, “Nearly bipartite graphs with large chromatic number,” Combinatorica 2.4 (1982), Theorem $1.5$.

Current status (as of May 2026): Rödl’s published construction settles the question negatively, with $f_r(n)=o(n)$ for every fixed $r\ge 2$; a formalized version remains incomplete.