Coloring triangle-free graphs on surfaces

Coloring triangle-free graphs on surfaces

-
Robin Thomas, Georgia Institute of Technology
Fine Hall 224

Let S be a fixed surface, and let k and q be fixed integers. Is there a polynomial-time algorithm that decides whether an input graph of girth at least q drawn in S is k-colorable? This question has been studied extensively during the last 15 years. We will briefly survey known results.Then we will describe a solution to one of the two cases left open (the prospects for the other one are not bright). For every surface S we give a polynomial-time algorithm that computes the chromatic number of an input triangle-free graph G drawn in S. The new contribution here is deciding whether G is 3-colorable, and has two main ingredients. The first is a coloring extension theorem that makes use of disjoint paths in order to construct a coloring. The notion of "winding number" of a 3-coloring plays an important role. The second ingredient is a theorem bounding the number and sizes of faces of size at least four in 4-critical triangle-free graphs on a fixed surface, a generalization of a theorem of Thomassen.
By developing more structure theory and using the notion of bounded expansion of Nesetril and Ossona de Mendez we were able to implement the algorithm to run in linear time. This is joint work with Zdenek Dvorak and Daniel Kral.