Three-coloring triangle-free graphs on surfaces

Robin Thomas
Georgia Institute of Technology

We study 4-critical graphs on surfaces and deduce several consequences, including a polynomial-time algorithm to 3-color triangle-free graphs on a fixed surface and a generalization of Grotzsch's theorem. This is joint work with Z. Dvorak and D. Kral.

Back to Combinatorics Tutorials