Show simple item record

dc.contributor.authorNorine, Sergueien_US
dc.date.accessioned2005-09-16T15:16:24Z
dc.date.available2005-09-16T15:16:24Z
dc.date.issued2005-07-20en_US
dc.identifier.urihttp://hdl.handle.net/1853/7232
dc.description.abstractThe first result of this thesis is a generation theorem for bricks. A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of a decomposition procedure of Kotzig, and Lovasz and Plummer. We prove that every brick except for the Petersen graph can be generated from K_4 or the prism by repeatedly applying certain operations in such a way that all the intermediate graphs are bricks. We use this theorem to prove an exact upper bound on the number of edges in a minimal brick with given number of vertices and to prove that every minimal brick has at least three vertices of degree three. The second half of the thesis is devoted to an investigation of graphs that admit Pfaffian orientations. We prove that a graph admits a Pfaffian orientation if and only if it can be drawn in the plane in such a way that every perfect matching crosses itself even number of times. Using similar techniques, we give a new proof of a theorem of Kleitman on the parity of crossings and develop a new approach to Turan's problem of estimating crossing number of complete bipartite graphs. We further extend our methods to study k-Pfaffian graphs and generalize a theorem by Gallucio, Loebl and Tessler. Finally, we relate Pfaffian orientations and signs of edge-colorings and prove a conjecture of Goddyn that every k-edge-colorable k-regular Pfaffian graph is k-list-edge-colorable. This generalizes a theorem of Ellingham and Goddyn for planar graphs.en_US
dc.format.extent734632 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectPfaffian orientationsen_US
dc.subjectGraph theory
dc.subjectMatching theory
dc.subject.lcshPfaffian systemsen_US
dc.subject.lcshMatching theoryen_US
dc.subject.lcshGraph theoryen_US
dc.titleMatching structure and Pfaffian orientations of graphsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentAlgorithms, Combinatorics, and Optimizationen_US
dc.contributor.departmentMathematics
dc.description.advisorCommittee Chair: Thomas, Robin; Committee Member: Cook, William; Committee Member: Duke, Richard; 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