The Hajós conjecture asserts that every graph with chromatic number 
contains a graph subdivision
of the complete graph 
(Catlin 1979; Bondy and Murty 2008, p. 409).
It strengthens the Hadwiger conjecture, which requires only a graph minor isomorphic to the complete
graph 
.
The Hajós conjecture holds for 
, but Catlin (1979) constructed counterexamples for every
. In particular, the Catlin
graph has chromatic number 8 but contains
no graph subdivision of the complete
graph 
(Bondy and Murty 2008, p. 410).
The cases 
and 
remain open (Hayashi et al. 2025).
