NBIA Colloquium – Niels Bohr Institute - University of Copenhagen

Niels Bohr Institute > Calendar > 2010 > NBIA Colloquium

NBIA Colloquium

Title: Maps and graphs on surfaces
Speaker: Carsten Thomassen, Technical University of Denmark.

Abstract: p { margin-bottom: 0.21cm; }

Graph coloring is an extensively studied subject, partly because of its relation to optimization (time table problems). Graph coloring shows up in other contexts. For example, Lieb’s Square Ice Constant can be expressed in terms of colorings. One of the main sources of inspiration was the 4 Color Problem (now a theorem). In 1890 Heawood considered the analogue for higher surfaces. This problem, known as the Heawood map color theorem, was settled by Ringel and Youngs in 1968. For example, the number of colors needed in the projective plane and the Klein bottle is 6. For the torus it is 7, etc. Although these numbers tend to infinity, there is a 5-color theorem for each surface in the following sense: For every surface S, there exist a finite number of (forbidden) graphs such that an arbitrary graph on S can be 5-colored if and only if it does not contain one of the forbidden graphs as a subgraph. There is no 4-color theorem of this type. In the talk these and related results will be discussed.