Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations
arXiv:1509.01013
Abstract
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.
32 pages, no figures; updated for reviewer comments