Georgia Institute of Technology College of Sciences

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grotzsch Theorem that every planar triangle-free graph is 3-colorable. We use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grunbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable. Joint work with O. Borodin, A. Kostochka and M. Yancey.

Every subcubic triangle-free graph on n vertices contains an independent set of size at least 5n/14 (Staton'79). We strengthen this result by showing that all such graphs have fractional chromatic number at most 14/5, thus confirming a conjecture by Heckman and Thomas. (Joint work with J.-S. Sereni and J. Volec)

The Weak Structure Theorem of Robertson and Seymour is the cornerstone of many of the algorithmic applications of graph minors techniques. The theorem states that any graph which has both large tree-width and excludes a fixed size clique minor contains a large, nearly planar subgraph. In this talk, we will discuss a new proof of this result which is significantly simpler than the original proof of Robertson and Seymour. As a testament to the simplicity of the proof, one can extract explicit constants to the bounds given in the theorem. We will assume no previous knowledge about graph minors or tree-width. This is joint work with Ken Kawarabayashi and Robin Thomas

We will discuss how linear isoperimetric bounds in graph coloring lead to new and interesting results. To that end, we say a family of graphs embedded in surfaces is hyperbolic if for every graph in the family the number of vertices inside an open disk is linear in the number of vertices on the boundary of that disk. Similarly we say that a family is strongly hyperbolic if the same holds for every annulus. The concept of hyperbolicity unifies and simplifies a number of known results about coloring graphs on surfaces while resolving some open conjectures. For instance: we have shown that the number of 6-list-critical graphs embeddable on a fixed surface is finite, resolving a conjecture of Thomassen from 1997; that there exists a linear time algorithm for deciding 5-choosability on a fixed surface; that locally planar graphs with distant precolored vertices are 5-choosable (which was conjectured for planar graphs by Albertson in 1999 and recently resolved by Dvorak, Lidicky, Mohar and Postle); that for every fixed surface, the number of 5-list-colorings of a 5-choosable graph is exponential in the number of vertices. We may also adapt the theory to 3-coloring graphs of girth at least five on surface to show that: the number of 4-list-critical graphs of girth at least five on a fixed surface is finite; there exists a linear time algorithm for deciding 3-choosability of graph of girth at least five on a fixed surface; locally planar graphs of girth at least five whose cycles of size four are far apart are 3-choosable (proved for the plane by Dvorak and related to the recently settled Havel's conjecture for triangle-free graphs in the plane). This is joint work with Robin Thomas.