Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations
Zdenĕk Dvořák, Daniel Král͏̌, Robin B. Thomas · arXiv (Cornell University) · 2015
We give a linear-time algorithm to decide 3-colorability (and find a 3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm also allows to prescribe the coloring for a bounded number of vertices.