3-colourability of ternary graphs

Status open high confidence

The conjecture that all ternary graphs (graphs with no induced cycle of length divisible by 3) are 3-colourable remains open. Bonamy, Charbit and Thomassé proved that ternary graphs have bounded chromatic number (arXiv:1408.2172), and Chudnovsky, Scott, Seymour and Spirkl extended this to graphs avoiding induced cycles of any fixed residue class. A proposed approach via a question of Král’ (whether every ternary graph has an edge whose deletion preserves being ternary, which would imply 3-colourability) was ruled out by Wrochna’s counterexample, but this does not disprove 3-colourability itself. No paper resolving whether the chromatic number bound can be taken to be exactly 3 was found.

Reviewer notes. No follow-up resolving the 3-colourability question was found in the indexed literature. The bounded-chromatic-number result (Bonamy-Charbit-Thomassé, arXiv:1408.2172) and the more general Chudnovsky-Scott-Seymour-Spirkl result on holes of specific residue (Combinatorica 2020, arXiv series) establish finiteness of the chromatic bound but leave open whether 3 suffices. A natural approach via Král’s edge-deletion question was disproved by Wrochna, removing one plausible proof strategy without settling the conjecture.

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