Show simple item record

dc.contributor.authorPostle, Luke Jamisonen_US
dc.date.accessioned2013-01-17T21:21:02Z
dc.date.available2013-01-17T21:21:02Z
dc.date.issued2012-08-23en_US
dc.identifier.urihttp://hdl.handle.net/1853/45807
dc.description.abstractThomassen 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. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general paradigm is established which improves a number of previous results while resolving several open conjectures. In addition, the proofs are almost entirely self-contained. In what follows, let S be a fixed surface, G be a graph embedded in S and L a list assignment such that, for every vertex v of G, L(v) has size at least five. First, the thesis provides an independent proof of a theorem of DeVos, Kawarabayashi and Mohar that says if G has large edge-width, then G is 5-list-colorable. Moreover, the bound on the edge-width is improved from exponential to logarithmic in the Euler genus of S, which is best possible up to a multiplicative constant. Second, the thesis proves that there exist only finitely many 6-list-critical graphs embeddable in S, solving a conjecture of Thomassen from 1994. Indeed, it is shown that the number of vertices in a 6-list-critical graph is at most linear in genus, which is best possible up to a multiplicative constant. As a corollary, there exists a linear-time algorithm for deciding 5-list-colorability of graphs embeddable in S. Furthermore, we prove that the number of L-colorings of an L-colorable graph embedded in S is exponential in the number of vertices of G, with a constant depending only on the Euler genus g of S. This resolves yet another conjecture of Thomassen from 2007. The thesis also proves that if X is a subset of the vertices of G that are pairwise distance Omega(log g) apart and the edge-width of G is Omega(log g), then any L-coloring of X extends to an L-coloring of G. For planar graphs, this was conjectured by Albertson and recently proved by Dvorak, Lidicky, Mohar, and Postle. For regular coloring, this was proved by Albertson and Hutchinson. Other related generalizations are examined.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectGraph coloringen_US
dc.subjectList-coloringen_US
dc.subjectChoosabilityen_US
dc.subject.lcshGraph theory
dc.subject.lcshGraph coloring
dc.title5-list-coloring graphs on surfacesen_US
dc.typeDissertationen_US
dc.description.degreePhDen_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Thomas, Robin; Committee Member: Cook, William; Committee Member: Dvorak, Zdenek; Committee Member: Trotter, William T.; Committee Member: Yu, Xingxingen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record