dc.contributor.author Norine, Serguei en_US dc.date.accessioned 2005-09-16T15:16:24Z dc.date.available 2005-09-16T15:16:24Z dc.date.issued 2005-07-20 en_US dc.identifier.uri http://hdl.handle.net/1853/7232 dc.description.abstract The first result of this thesis is a generation theorem for en_US 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. dc.format.extent 734632 bytes dc.format.mimetype application/pdf dc.language.iso en_US dc.publisher Georgia Institute of Technology en_US dc.subject Pfaffian orientations en_US dc.subject Graph theory dc.subject Matching theory dc.subject.lcsh Pfaffian systems en_US dc.subject.lcsh Matching theory en_US dc.subject.lcsh Graph theory en_US dc.title Matching structure and Pfaffian orientations of graphs en_US dc.type Dissertation en_US dc.description.degree Ph.D. en_US dc.contributor.department Algorithms, Combinatorics, and Optimization en_US dc.contributor.department Mathematics dc.description.advisor Committee Chair: Thomas, Robin; Committee Member: Cook, William; Committee Member: Duke, Richard; Committee Member: Trotter, William T.; Committee Member: Yu, Xingxing en_US
﻿