Georgia Institute of Technology College of Sciences

Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. We develop new techniques to prove a general theorem for 5-list-coloring graphs embedded on a fixed surface. Namely, for every surface S and every integer C > 0, there exists D such that the following holds: Let G be a graph embedded in a surface S with edge-width at least D and a list assignment L such that, for every vertex v in G, L(v) has size at least five. If F is a collection of any number of facial cycles of length at most C such that every two cycles in F are distance at least D apart and every cycle in F has a locally planar neighborhood up to distance D/2, then any proper L-coloring of F extends to an L-coloring of G. This theorem implies the following results. In what follows, let S be a fixed surface, G be a graph embedded in S (except in 4, where G is drawn in S) and L a list assignment such that, for every vertex v of G, L(v) has size at least five. 1. If G has large edge-width, then G is 5-list-colorable. (Devos, Kawarabayashi and Mohar) 2. There exists only finitely many 6-list-critical graphs embeddable in S. (Conjectured by Thomassen, Proof announced by Kawarabayashi and Mohar) As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable on S. Furthermore, we exhibit an explicit bound on the size of such graphs. 3. There exists D(S) such that the following holds: If X is a subset of the vertices of G that are pairwise distance at least D(S) apart, then any L-coloring of X extends to an L-coloring G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. 4. There exists D(S) such that the following holds: If G is a graph drawn in S with face-width at least D(S) such that any pair of crossings is distance at least D apart, then G is L-colorable. For planar graphs, this was recently proved by Dvorak, Lidicky and Mohar. Joint work with Robin Thomas.