Polynomial-time 4-colorability on fixed surfaces

Status open high confidence

The question of whether 4-colorability of graphs embedded in a fixed surface can be tested in polynomial time remains open as of May 2026. Dvořák, Král, and Thomas identify this as the sole remaining open step in Thomassen's polynomial-time colorability program, having resolved the 3-coloring case for triangle-free graphs on surfaces. No polynomial-time algorithm for deciding 4-colorability on fixed surfaces in general has been established; recent work by Briański, Kráľ, Lamaison, and Shu (2024) makes structural progress on 4-colorability of Eulerian triangulations of the torus but does not address the algorithmic question.

Cited literature (1)

• partial Four-coloring Eulerian triangulations of the torus (2024)
  Briański, M., Kráľ, D., Lamaison, A., Shu, X. · arXiv preprint · arXiv:2409.19165

  Proves every Eulerian triangulation of the torus with representativity at least 10 is 4-colorable (and shows the bound is nearly tight), a structural result for a restricted class on a fixed surface that does not resolve the polynomial-time algorithmic question.

Reviewer notes. No follow-up resolving the polynomial-time complexity of 4-colorability on fixed surfaces was found. The paper arXiv:2409.19165 (Briański–Kráľ–Lamaison–Shu, 2024) proves structural 4-colorability for Eulerian triangulations of the torus with representativity ≥ 10 but does not address the algorithmic complexity question. The authors themselves judged prospects for near-term resolution as 'not very bright'.

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