Brandt–Thomassé problem on triangle-free graphs

The problem asks whether every triangle-free graph on $n$ vertices with minimum degree greater than $n/3$ has chromatic number at most $4$. Erdős and Simonovits posed the stronger $3$-color version in 1973; Häggkvist refuted it, and Brandt and Thomassé announced the $4$-color result in 2005.

Known results

• Erdős and Simonovits, 1973: conjectured $3$-colorability under minimum degree greater than $n/3$.
• Häggkvist: constructed a $4$-chromatic counterexample to that conjecture.
• Brandt and Thomassé, 2005: proved the $4$-color conclusion, originally in an unpublished manuscript.
• Thomassen, 1999: established bounded chromatic number when the minimum degree is at least $cn$ for every $c>1/3$.

September 2026 preprint

Jiaao Li and Xinyuan Li's paper Bounded chromatic number of graphs with small clique number and large minimum degree reports a resolution at the threshold $\delta$(G)>n/3$, together with near-threshold and$K_r$-free extensions. This claim is based on an unrefereed preprint and is therefore unverified.

Current status (as of September 2026): The $4$-color conclusion at minimum degree greater than $n/3$ is claimed settled, but the new preprint has not been independently verified.