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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7232 |
| Date | 20 July 2005 |
| Creators | Norine, Serguei |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 734632 bytes, application/pdf |
Page generated in 0.0022 seconds