Linear-time 3-coloring output on surfaces
Open Problem (linear-time 3-coloring output) · arXiv:1601.01197
Status open high confidence
The source paper (arXiv:1601.01197, JCTB 2022) achieves a linear-time decision algorithm (Theorem 1.3) and a quadratic-time output algorithm (Theorem 1.4) for 3-coloring triangle-free graphs embedded in a fixed surface with a bounded number of precolored boundary vertices. The open problem asks whether the output step can also be made linear-time using ideas analogous to the decision algorithm. Five targeted web searches found no follow-up paper resolving this question; the problem appears to remain open as of May 2026.
Reviewer notes. No follow-up paper addressing the linear-time output step was found. The Part VI paper (Three-coloring triangle-free graphs on surfaces VI, JCTB 2023) treats 3-colorability of quadrangulations but does not appear to resolve this specific algorithmic question. The conjecture is technically narrow (improving a quadratic-time algorithm to linear-time for the output phase) and may require significant additional technical machinery beyond what the decision algorithm uses.
Context
Theorem 1.4 gives a quadratic-time algorithm to output a 3-coloring in the affirmative case. The authors believe a linear-time algorithm for the output step exists via ideas analogous to those of the linear-time decision algorithm (Theorem 1.3), but note significant technical challenges in realising it.
Notes. Stated in running prose in the introduction: 'we believe that there exists a linear-time algorithm to output a 3-coloring using ideas similar to those of Theorem 1.3; however, there are significant technical challenges in designing it and we leave this as an open problem.' No labelled theorem environment.
Source paper
Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm
Zdenek Dvorak, Daniel Kral, Robin Thomas · 2020-11-05
https://arxiv.org/abs/1601.01197
PDF source