4-colorability on fixed surfaces complexity
Open Problem: polynomial-time 4-colorability on fixed surfaces · arXiv:1010.2472
Status open high confidence
The question of whether 4-colorability of graphs on a fixed surface (other than the sphere) admits a polynomial-time algorithm remains open as of 2026. By contrast, 5-colorability on any fixed surface can be decided in linear time (via finiteness of 6-critical graphs), and 3-colorability of triangle-free graphs on any fixed surface can be decided in linear time (Dvořák, Král, Thomas, Part VII of this series). The structural paper arXiv:1801.10457 on irreducible 4-critical triangle-free toroidal graphs provides structural insight but does not resolve the algorithmic question. No follow-up paper resolving this problem was found in the published literature.
Reviewer notes. The analogous 3-colorability (triangle-free) and 5-colorability questions on fixed surfaces are both resolved in polynomial (linear) time. The 4-colorability question is explicitly stated open by the authors with the remark that the techniques currently available do not give much hope for a positive resolution in the near future. No follow-up paper resolving this problem was found after exhaustive search.
Context
The authors note that while 5-colorability on any fixed surface can be decided in polynomial (even linear) time using the finiteness of 6-critical graphs (Theorem 1), the analogous question for 4-colorability is open, and the techniques currently available do not give much hope for a positive resolution in the near future.
Also stated in
- Irreducible 4-critical triangle-free toroidal graphs (2018-01-31)
Notes. Stated in prose without a labelled theorem environment; presented as a known open problem in the field rather than a novel conjecture of the authors. PDF source.
Source paper
Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle
Zdenek Dvorak, Dan Kral, Robin Thomas · 2016-03-04
https://arxiv.org/abs/1010.2472
PDF source