Instructor: Robin Thomas
Textbook: None. I have not found a suitable book. References
will be provided.
Some texts you may wish to consult:
Diestel, Graph Theory
Bollobas, Modern Graph Theory
West, Introduction to Graph Theory
Bondy and Murty, Graph Theory
Even, Graph Algorithms
Golumbic, Algorithmic Graph Theory and Perfect Graphs
Cook, Cunningham, Pulleyblank and Schrijver, Combinatorial Optimization
Possible topics:
*Connectivity: Vertex- and edge-disjoint paths in graphs, the disjoint
2 paths problem, testing connectivity, decomposing a graph into
3-connected components (Tutte's cleavage units) in linear time,
edge-disjoint spanning trees, edge-connectivity, splitting off
vertices, Gomory-Hu trees, tangles and brambles in graphs and the
canonical tree-decomposition they generate, connectivity augmentation
*Matching: Review of Edmonds' blossom algorithm and Edmonds' matching
polyhedron theorem, the Chinese postman problem, T-cuts and T-joins,
Pfaffian orientations and their applications
*Coloring: Schrijver's bipartite edge-coloring algorithm, 5-coloring
planar graphs in linear time, choosability
*Testing planarity: A linear-time planarity test, testing embeddability
in surfaces
*Perfect graphs: Basic properties, recognition, optimization on perfect
graphs, applications
*Graph classes: Interval graphs, chordal graphs, split graphs,
permutation graphs, threshold graphs, comparability graphs,
intersection graphs of geometric objects. Properties, recognition and
optimization.
*Directed graphs: Testing connectivity of digraphs, splitting off
vertices, connectivity augmentation, disjoint directed cycles, even
cycles, disjoint branchings, the Lucchesi-Younger theorem
*Tree-width: Basic properties, linear-time algorithms for problems on
graphs of bounded tree-width, applications
*Separators: The Lipton-Tarjan separator theorem, separators in graphs
with an excluded minor, applications
*Graph Minors: The Graph Minor Theorem, The disjoint paths algorithm,
polynomial-time algorithms for various problems when the input graph
excludes a certain minor
Grades: Each student will be required to scribe several lectures. A combination of homework, exam, and a presentation (in class, in a seminar or in private).
Final exam. Due before 3:05PM, April 29, 2009.
Office hours: MW 2-3 and by appointment.
Office: 217B Skiles.
Lecture archive:
January 7: Introduction to Pfaffian orientations. Handout was provided.