Hajós conjecture for $k = 5$ and $k = 6$

Status open high confidence

The Hajós conjecture — that every k-chromatic graph contains a subdivision of K_k — remains open for k = 5 and k = 6. The conjecture holds for k ≤ 4 (Dirac 1952) and was disproved by Catlin (1979) for every k ≥ 7, leaving k = 5 and k = 6 as the only unresolved cases. A line of structural work on Hajós graphs (minimal 5-chromatic graphs without a K_5-subdivision) is ongoing, aiming to reduce the k = 5 case to the Four Color Theorem, but the full conjecture for both k = 5 and k = 6 remains open as of September 2026.

Cited literature (1)

• partial 4-Separations in Hajós Graphs (2020)
  unknown (not retrieved) · arXiv preprint · arXiv:2004.12468

  Proves structural results about 4-separations in Hajós graphs (minimal 5-chromatic graphs without K_5-subdivision), described by the authors as a step toward reducing Hajós' conjecture (k = 5 case) to the Four Color Theorem.

Reviewer notes. The book states Catlin (1979) disproved Hajós' conjecture for k ≥ 7; some survey sources say k ≥ 6, but the consensus is that k = 5 and k = 6 are both open. A Cal State master's thesis titled 'On the Fifth Case of the Hajós Conjecture' was found in searches but the PDF was inaccessible (HTTP 403); it likely contains partial results rather than a full proof (no published journal paper resolving k = 5 was found). The OPG corpus record 'coloring_and_immersion' tracks the immersion analogue (every graph contains an immersion of K_{χ(G)}), which is a distinct, weaker statement; arXiv:2303.06483 concerns that immersion variant, not the subdivision (Hajós) conjecture studied here.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).