Title: Coloring triangle-free graphs on surfaces
Speaker: Robin Thomas, Georgia Tech
When: February 28, 12:30-13:30
Where: Porter Hall 125B
Abstract:
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. In the first part of the talk we will survey known results. In the second part of the talk we 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 is obtained using a coloring extension theorem that in turn makes use of disjoint paths in order to construct a coloring. The notion of “winding number” of a 3-coloring plays an important role. This is joint work with Zdenek Dvorak and Daniel Kral.
