Type of Document	Dissertation
Author	Norine, Serguei
URN	etd-06132005-120146
Title	Matching structure and Pfaffian orientations of graphs
Degree	Doctor of Philosophy
Department	Algorithms, Combinatorics and Optimization
Advisory Committee	Advisor Name Title Thomas, Robin Committee Chair Cook, William Committee Member Duke, Richard Committee Member Trotter, William T. Committee Member Yu, Xingxing Committee Member
Keywords	Pfaffian orientations graph theory matching theory
Date of Defense	2005-05-25
Availability	unrestricted
Abstract The 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    norine_serguei_200508_phd.pdf 734.63 Kb 00:03:24 00:01:44 00:01:31 00:00:45 00:00:03