Show simple item record

dc.contributor.advisorThomas, Robin
dc.contributor.authorWhalen, Peter
dc.date.accessioned2014-08-27T13:33:20Z
dc.date.available2014-08-27T13:33:20Z
dc.date.created2014-08
dc.date.issued2014-04-28
dc.date.submittedAugust 2014
dc.identifier.urihttp://hdl.handle.net/1853/52207
dc.description.abstractThe first result of this thesis is a partial result in the direction of Steinberg's Conjecture. Steinberg's Conjecture states that any planar graph without cycles of length four or five is three colorable. Borodin, Glebov, Montassier, and Raspaud showed that planar graphs without cycles of length four, five, or seven are three colorable and Borodin and Glebov showed that planar graphs without five cycles or triangles at distance at most two apart are three colorable. We prove a statement that implies the first of these theorems and is incomparable with the second: that any planar graph with no cycles of length four through six or cycles of length seven with incident triangles distance exactly two apart are three colorable. The third and fourth chapters of this thesis are concerned with the study of Pfaffian orientations. A theorem proved by William McCuaig and, independently, Neil Robertson, Paul Seymour, and Robin Thomas provides a good characterization for whether or not a bipartite graph has a Pfaffian orientation as well as a polynomial time algorithm for that problem. We reprove this characterization and provide a new algorithm for this problem. In Chapter 3, we generalize a preliminary result needed to reprove this theorem. Specifically, we show that any internally 4-connected, non-planar bipartite graph contains a subdivision of K3,3 in which each path has odd length. In Chapter 4, we make use of this result to provide a much shorter proof using elementary methods of this characterization. In the fourth and fifth chapters we investigate flat embeddings. A piecewise-linear embedding of a graph in 3-space is flat if every cycle of the graph bounds a disk disjoint from the rest of the graph. We provide a structural theorem for flat embeddings that indicates how to build them from small pieces in Chapter 5. In Chapter 6, we present a class of flat graphs that are highly non-planar in the sense that, for any fixed k, there are an infinite number of members of the class such that deleting k vertices leaves the graph non-planar.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectCombinatorics
dc.subjectColoring
dc.subjectGraph theory
dc.subjectPfaffian orientations
dc.subjectFlat embeddings
dc.titlePfaffian orientations, flat embeddings, and Steinberg's conjecture
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentMathematics
thesis.degree.levelDoctoral
dc.contributor.committeeMemberYu, Xingxing
dc.contributor.committeeMemberNorin, Sergey
dc.contributor.committeeMemberTrotter, William
dc.contributor.committeeMemberVazirani, Vijay
dc.date.updated2014-08-27T13:33:20Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record