Math 8863 Topics in Graph Theory, Spring 2006
Instructor: Robin Thomas
Recommended texts:
[D] Diestel, Graph Theory
[B] 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 lectures (here is a template
for the notes)
- turn in 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
Long-term plan: Below please find a list of topics that I plan
to do at some point, but obviously not all can be covered in a
semester course.
This year I plan to cover topics (5), (9), (10), (11), (13),
but other suggestions are welcome.
Material covered:
Click here. Here is a
link to what we did last year.
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. Coloring graphs on surfaces.
(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.
(9) The structure of 3-connected graphs and excluded minor theorems
(10) 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.
(11) 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.
(12) Spacial embeddings and spectral graph invariants. Linkless and
knotless embeddings, Colin de Verdiere's invariant, their relationship
and open problems.
(13) 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.
(14) The Caccetta-Haggkvist conjecture. The conjecture and its relatives,
some known results, relation to additive number theory.
(15) Perfect graphs. This is a huge subject.