Back to search

Georgia Institute of Technology

Matching structure and Pfaffian orientations of graphs

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Algorithms, Combinatorics, and Optimization
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Norine, Serguei
Advisor dc:contributor.advisor
  • Thomas, Robin
Committee members dc:contributor.committeemember
  • Cook, William
  • Duke, Richard
  • Trotter, William T.
  • Yu, Xingxing

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/7232

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Norine, Serguei. Matching structure and Pfaffian orientations of graphs. Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/7232