Coloring near-quadrangulations of the torus

The 3-colorability of triangle-free graphs is always guaranteed for graphs embedded in the plane, while NP-complete when triangles are allowed. It is known that in general for any surface, deciding 3-colorability of triangle-free graphs cannot be algorithmically hard and can be reduced to 3-coloring of near-quadrangulations of the given surface. However only for the plane and the projective plane a nice characterization of 3-colorability was known. Our focus is on the graphs embedded in the torus. We design an algorithm capable of deciding 3-colorability of near-quadrangulations in a reasonable time. Based on this result, we derive further characteristics necessary for a triangle-free graph embedded in the torus to not have a 3-coloring and design a practical algorithm for 3-coloring triangle-free graphs embedded in the torus. Based on our ideas, an algorithm for general surfaces was later derived.

Joint work with Zdeněk Dvořák