Matching structure and Pfaffian orientations of graphs

Pfaffian orientations;Graph theory;Matching theory

Norine, Serguei ; Algorithms, Combinatorics, and Optimization Mathematics

University:Georgia Institute of Technology

Department:Algorithms, Combinatorics, and Optimization

关键词: Pfaffian orientations;    Graph theory;    Matching theory;   

Others  :  https://smartech.gatech.edu/bitstream/1853/7232/1/norine_serguei_200508_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The first result of this thesis isa generation theorem forbricks. A brick is a 3-connected graph such that the graphobtained from it by deleting any two distinct vertices has aperfect matching. The importance of bricks stems from the factthat they are building blocks of a decomposition procedure ofKotzig, and Lovasz and Plummer. We prove that every brick exceptfor the Petersen graph can be generated from K_4 or the prism byrepeatedly applying certain operations in such a way that all theintermediate graphs are bricks. We use this theorem to prove anexact upper bound on the number of edges in a minimal brick withgiven number of vertices and to prove that every minimal brick hasat least three vertices of degree three.The second half of the thesis is devoted to an investigation ofgraphs that admit Pfaffian orientations. We prove that a graphadmits a Pfaffian orientation if and only if it can be drawn inthe plane insuch a way that every perfect matching crossesitself even number of times. Using similar techniques, we give anew proof of a theorem of Kleitman on the parity of crossings anddevelop a new approach to Turan's problem of estimating crossingnumber of complete bipartite graphs.We further extend our methods to study k-Pfaffian graphs andgeneralize a theorem by Gallucio, Loebl and Tessler. Finally, werelate Pfaffian orientations and signs of edge-colorings and provea conjecture of Goddyn that every k-edge-colorable k-regularPfaffian graph is k-list-edge-colorable. This generalizes atheorem of Ellingham and Goddyn for planar graphs.