Triangle-free χ additive approximation in minor-closed

Status open medium confidence

The open question—whether a uniform additive approximation for the chromatic number of triangle-free graphs exists across all proper minor-closed classes—remains unresolved. The source paper (Dvořák and Kawarabayashi, ICALP 2018) establishes hardness for K_{4k+1}-minor-free graphs in general, and a weaker hardness bound for K_{4k+1}-minor-free graphs with no K_4 cliques (Theorem 6), but explicitly leaves the triangle-free case open. No follow-up paper resolving this question was found in a wide web search across the 2017–2026 period.

Reviewer notes. No follow-up paper resolving the triangle-free open question was found. The published version of the source paper appeared at ICALP 2018 (LIPIcs vol. 107, article 47) and in Journal of Combinatorial Theory Series B (ScienceDirect, 2020). The known positive special case is that every triangle-free K_5-minor-free graph is 3-colorable (extending Grötzsch's theorem), but this does not address the uniform additive approximation across all proper minor-closed classes. Confidence is medium because the conjecture is roughly 9 years old, so absence of a resolution in the search is somewhat suspicious; the question may simply be very hard.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).