SFU Discrete Math Seminar: Zdenek Dvorak

A graph drawn in a surface is a k-near-quadrangulation if the product of the lengths of its faces, except for 4-faces, is at most k. Near-quadrangulations play a fundamental role in the theory of 3-colorability of triangle-free graphs on surfaces. We show how the well-known duality between colorings and flows can be used to design

(1) a 3-precoloring extension algorithm for k-near-quadrangulations of the plane, and

(2) a 3-coloring algorithm for k-near-quadrangulations of the torus,

with time complexity polynomial in k and the number of vertices. This is joint work with C. Bang, E. Heath, and B. Lidicky.