High-chromatic subgraph with large average degree

Status open medium confidence

Conjecture 6 from arXiv:1808.01605, asserting that high chromatic number forces a subgraph of girth at least g with average degree at least k for all k and g, remains open in full generality. The source paper itself establishes the g=4 case (triangle-free subgraphs with large fractional chromatic number), and the g=3 case is trivial via the degeneracy bound. No follow-up paper resolving or substantially advancing the g≥5 cases was found in a targeted web search through 2026.

Reviewer notes. No follow-up found in indexed literature. The conjecture is a weakening of the Erdős–Hajnal conjecture (using chromatic number as hypothesis and requiring only large average degree, not large chromatic number, in the subgraph). The g=3 case is trivially true by degeneracy; the g=4 case is proved in the source paper. The Keevash–Li–Mohar preprint 'Digraph girth via chromatic number' (Mohar is a co-author) appeared in search results but treats directed graphs and could not be read in full. arXiv:2605.02543 (2026) proves a different variant of Thomassen's conjecture (highly connected subgraphs with large chromatic number), not girth/average-degree. Confidence is medium rather than high because the conjecture is 7 years old and absence of indexed evidence for an open problem of this age carries moderate uncertainty.

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