Show simple item record

dc.contributor.authorYerger, Carl Roger, Jr.en_US
dc.date.accessioned2011-03-04T20:22:16Z
dc.date.available2011-03-04T20:22:16Z
dc.date.issued2010-08-23en_US
dc.identifier.urihttp://hdl.handle.net/1853/37197
dc.description.abstractA graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectGraphsen_US
dc.subjectColoringen_US
dc.subjectSteinbergen_US
dc.subjectCriticalen_US
dc.subject.lcshGraph theory
dc.subject.lcshGraph coloring
dc.titleColor-critical graphs on surfacesen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Robin Thomas; Committee Member: Asaf Shapira; Committee Member: William Cook; Committee Member: William T. Trotter; Committee Member: XingXing Yuen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record