Math 8863 Topics in Graph Theory, Spring 2005

Instructor: Robin Thomas

Recommended texts: Diestel, Graph Theory and Bollobás, Modern Graph Theory

Prerequisite: Math 6014 Graph Theory

Requirements: Students registering for credit will be expected to do some (but not necessarily all) of the following:

solve an open problem
scribe several lectures (here is a template for the notes)
turn in several take-home assignments
do independent research on one of the topics suggested in class (independently or in small groups)
present a research paper in class or in a seminar

Lecture schedule: Below please find a tentative list of topics as announced at the beginning of the semester, and here is the actual lecture schedule. Most of the basic topics can be found in one of the recommended texts. Not all the topics listed can be covered. Topics can be added and deleted according to students' interests. Please let me know if you have any preferences. Here are transparencies for some of the talks I have given on various occassions.

Basic Topics:

(1) Connectivity. Disjoint paths, disjoint spanning trees, Mader's H-Wege theorem and other minimax theorems.

(2) Matching. The Edmonds-Gallai decomposition, Edmonds matching polytope theorem, decomposition into bricks and braces, Pfaffian orientations, T-joins and T-cuts.

(3) Planar graphs. Characterizations of planarity, Whitney's theorem, planar duality, separators

(4) Nowhere zero flows. Flow-coloring duality, the existence of nowhere zero 6-flows, the 3-flow, 4-flow and 5-flow conjecture.

(5) Coloring. List coloring. Galvin's proof of Dinitz' conjecture, the algebraic method of Alon and Tarsi, Thomassen's proof that planar graphs are 5-choosable.

(6) Extremal problems. Szemeredi's regularity lemma and applications, the Erdos-Stone theorem, extremal problems for minors and linkages

(7) Tree-width and applications. Tree-decompositions, excluding a grid, applications to the Erdos-Posa problem, algorithmic applications.

(8) The Tutte polynomial. Definition, evaluations of the Tutte polynomial, the Jones polynomial of a link, other graph polynomials.

Additional topics:

(8) The structure of 3-connected graphs and excluded minor theorems

(9) More on planar graphs. Schnyder's theorem and drawing on a grid, a linear planarity algorithm, Tutte's theorem on the Hamiltonicity of 4-connected planar graphs.

(10) Graphs on surfaces. Classification of surfaces, orientability, duality, uniqueness of embeddings, combinatorial description of an embedding, representativity, excluded minors on a fixed surface, the map color theorem, chromatic number, disjoint paths on surfaces, Schrijver's theorems.

(11) Spacial embeddings and spectral graph invariants. Linkless and knotless embeddings, Colin de Verdiere's invariant, their relationship and open problems.

(12) Graph minors. The graph minor project of Robertson and Seymour, the excluded clique theorem, well-quasi-ordering of finite graphs by the graph minor relation, a polynomial-time algorithm for the k disjoint paths problem for fixed k, applications and open problems.

Above information accurate as of November 3, 2004.