I will be teaching a minicourse on Structural
Graph Theory at the Euler
Institute for Discrete Mathematics in Eindhoven, the Nethelands during the week June
6-10, 2005.
General prerequisites: Basic
notions and theorems of
graph theory such as the max-flow
min-cut theorem, Menger's theorem, Hall's theorem (matchings in
bipartite
graphs), Tutte's 1-factor theorem, Brooks' theorem, Vizing's theorem,
Planar graphs, Euler's formula, Kuratowski's theorem. The standard
references are [B, D].
Recommended reading:
Participants may wish to familiarize themselves with specific
concepts and notions ahead of each lecture. Please follow the links
below for details. The book [D] covers many of those; other
useful sources are [LP, RR, MT]. Those interested are welcome to
look at transparencies
for some of my earlier talks. Of these,
the NSF-CBMS lecture series is the most
relevant. I also have various lecture notes: on tree-decompositions,
on perfect
graphs, and on graph
structure theory.
Exercises: Here is a set of introductory exercises. Please follow the links
below for exercises associated with each lecture.
Lecture schedule:
- Planar graphs and graphs on surfaces. Review of basic
properties of
planar graphs, Kuratowski's theorem and the uniqueness of planar
embeddings. Brief discussion of Steinitz's theorem, circle packing,
Schnyder's theorem and drawing on a grid, and geometric graphs.
Wye-delta transformations and applications. Planar separators. The
emergence of planarity in graph structure theory, the two-paths
problem.
Graphs on surfaces, representativity (face-width). More
information...
- Tree-decompositions of graphs I.
Path-width, tree-width and applications to structure theory and the
design of
algorithms. The concept of a haven (bramble) as an obstacle to low
tree-width and its use. Excluding a planar graph. The Erdos-Posa
property. See also my notes on
tree-decompositions. More
information...
- Tree-decompositions of graphs II.
Branch-width and algorithms. The graph minor theorem and its
applications. More information...
- Excluded minor theorems and well-quasi-ordering.
Seymour's splitter theorem and its applications. Analogues for higher
connectivity and their applications. Separators. Typical subgraphs of
large graphs. Excluded minor theorems for infinite graphs (time
permitting). Well-quasi-ordering finite trees and extension to graphs
of bounded tree-width. The finitness of obstruction sets for surface
embeddings. More information...
- The Four-Color Theorem.
History, equivalent formulations and an outline of a proof. What are
the prospects for finding a computer-free proof? More
information...
- Beyond the Four-Color Theorem.
Unique coloring, edge-coloring, packing T-joins, nowhere-zero flows,
cycle double covers, Hadwiger's conjecture. Jorgensen's conjecture.
Extremal problems for minors. Linkages. More
information...
- Matching structure, Pfaffian orientations and digraph
structure I. Edmonds' matching theorem, the linear hull of perfect
matchings, the matching structure:
decomposition into bricks and braces, the matching lattice, Pfaffian
orientations and their use, Pfaffian orientations of bipartite graphs,
Polya's permanent problem, the even directed cycle
problem, sign-nonsingular matrices, applications in economics. More
information...
- Matching structure, Pfaffian orientations and digraph
structure II. Directed tree-width and digraph structure.
Generating bricks, Pfaffian orientations of bricks, relation to
parity of crossing numbers and signs of edge-colorings.
Matching width and its relation to directed tree-width. More
information coming.
- Perfect graphs. Examples of perfect graphs, communication
complexity,
graph entropy and applications, the perfect graph theorem of Lovasz,
polyhedral
aspects, relation to geometric optimization, graph entropy and
application
to sorting, the imperfection ratio and application to the channel
assignment
problem, stable matchings and the theorem of Gale and Shapley, 2-joins,
skew partitions and the Strong Perfect Graph Theorem. More information....
- To be determined. The possibilities include: More on any
of
the above topics, spatial embeddings of graphs, planarity in linear
time,
the structure of infinite graphs.
Relevant books:
[B] B. Bollobas, Modern Graph Theory
[D] R.
Diestel, Graph Theory, 2nd edition
[LP] L. Lovasz and M. Plummer, Matching theory
[MT] B. Mohar and C. Thomassen, Graphs and surfaces
[RR] A. Ramirez Alfonsin and B. Reed, Perfect graphs