Transparencies
for my lectures at the 2000 CIRM-DONET Workshop on Graph Theory
are now available at
http://www.math.gatech.edu/~thomas/SLIDE.
For reference purposes, here is my original tentative plan.
Topics on planarity and Hamiltonian graphs were not covered.
Graph planarity and related topics
I have given a similar lecture at the recent Graph Drawing conference.
You can look up my
transparencies
for that talk.
Tree-decompositions of graphs
See the
lecture notes written for the Catlin Memorial Workshop.
Planarity in linear time
Testing planarity is a fundamental algorithmic problem. There are
linear-time algorithms, but they are fairly complicated. My favorite
one is an algorithm by Shih and Hsu. I have written an
exposition
of their algorithm.
Linkless embeddings of graphs in 3-space
See N. Robertson, P. D. Seymour and R. Thomas,
Linkless embeddings of graphs in 3-space,
Bull. Amer. Math. Soc. 28 (1993), 84-89.
The Four-Color Theorem
Here is a brief
web survey,
and here is a
survey
that appeared in the Notices of the AMS.
Excluded minor theorems
Here are
transparencies
for a similar lecture I have given at the 17th British Combinatorial
conference, and here is the
survey paper.
Hadwiger's conjecture for K6-free graphs
See N. Robertson, P. D. Seymour and R. Thomas,
Hadwiger's conjecture for K6-free graphs,
Combinatorica 13 (1993), 279-361.
Tutte's edge 3-coloring conjecture
With N. Robertson, D. P. Sanders and P. D. Seymour we managed to
prove Tutte's edge 3-coloring conjecture that every 2-connected
cubic graph with no Petersen minor is edge 3-colorable. By a result
of Tait the conjecture implies the Four-Color Theorem. The proof
is long and will occupy five papers. One of the five papers
appeared in
N. Robertson, P. D. Seymour and R. Thomas,
J. Combin. Theory Ser. B. 70 (1997),
166-183.
Infinite graphs
With Robertson and Seymour we proved several structure theorems
for excluding infinite minors. See our survey paper in
N. Robertson, P. D. Seymour and R. Thomas,
Excluding infinite minors,
In: Directions in Infinite Graph Theory
and Combinatorics, R. Diestel ed., North-Holland, 1992.
There is also a
newer result.
Polya's permanent problem
This includes material for at least two lectures.
Here is the relevant
paper,
here is a relevant
website,
and here is an
abstract
for a talk I have given.
Hamiltonian graphs on surfaces
Tutte proved that every 4-connected planar graph is hamiltonian.
This talk will be about various extensions of this result.
See R. Thomas and X. Yu,
4-connected projective-planar graphs are Hamiltonian,
J. Combin. Theory Ser. B 62 (1994), 114-132 and
N. Dean, R. Thomas and X. Yu,
Spanning paths in infinite planar graphs,
J. Graph Thery 23 (1996), 163-174.
Digraph minors
Here are
transparencies
for a talk on directed tree-width, and here are
transparencies
for a talk I have given at the
most recent SODA conference.
Coloring graphs on surfaces
The relevant manuscripts are
Three-coloring Klein bottle graphs of girth five
(with Barrett Walls),
A new proof of the independence ratio of triangle-free cubic graphs
(with Christopher Carl Heckman),
Independent sets in triangle-free cubic planar graphs
(with Christopher Carl Heckman).