Instructor: Robin Thomas
Prerequisite: Math 6014 Graph Theory
Recommended text: B. Mohar and C. Thomassen, Graphs on surfaces
Requirements: Students registering for credit will be
expected
to do some (but not necessarily all) of the following:
Lecture plan. Rigorous treatment of planar graphs. Graphs on surfaces and graph minor structure theory, with emphasis on coloring graphs on surfaces. We will use the recommended book and then will proceed to cover recent results in the literature. This will lead to many open problems and will present areas suitable for thesis research.
January 8: Galvin's proof of Dinitz' conjecture.
January 10-29:
Planar graphs.
January 31:
A simple quadratic algorithm for testing planarity.
Notes by Carl Yerger.
February 5:
Excluded minors for the projective plane I.
Notes by Subramanyam Kalyanasundaram.
February 7:
Excluded minors for the projective plane II.
Notes by Daniel Steffy.
February 12:
Excluded minors for the projective plane III.
Notes by Danupon Nanongkai.
February 14:
The classification of surfaces I. No scribe notes. The material is covered
in the Mohar-Thomassen book. The exposition in class followed
the book W.S.Massey, A basic course in algebraic topology.
February 19:
Colloquium by Madhu Sudan.
February 21:
The classification of surfaces II.
See Massey's book.
February 26:
Cutting open a surface along a cycle.
February 28:
Euler's formula.
March 5:
Non-orientable embeddings
March 7:
The genus of a graph
March 12:
Introduction to face-width.
Notes by Amanda Pascoe.
March 14:
Graph embeddings of face-width 2 and 3.
Notes by Amanda Pascoe.
Homework 1 due before 3:05PM on April 3.
April 2:
Coloring triangle-free graphs in the projective plane.
April 4:
Survey of coloring graphs on surfaces.
Notes by Yan Shu.
April 9:
List coloring, also known as choosability.
Notes by Alejandro Torielo.
April 11:
5-critical graphs on surfaces and some open problems.
Notes by Noah Streib.
April 18:
Grotzsch's theorem, following [C. Thomassen,
Grotzsch's 3-color theorem and its counterparts
for the torus and the projective plane, J. Combin. Theory Ser. B
62 (1994), 268-279.]
Homework 2 due before 3:05PM on May 2.
April 23:
Grotzsch's theorem, continued. The theorem of Fiedler, Huneke, Richter and
Robertson about orientable genus of graphs embedded in the projective plane.
See Mohar-Thomassen, Section 5.8.