BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Maps and graphs on surfaces - Professor C Thomassen (Technical Uni
 versity of Denmark)
DTSTART:20080529T160000Z
DTEND:20080529T170000Z
UID:TALK12391@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Graph coloring is a extensively studied subject\, partly becau
 se of its relation to optimization (time table problems). One of the main 
 sources of inspiration was the 4 Color Problem (now a theorem). In 1890 He
 awood 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 te
 nd to infinity\, there is a 5 color theorem for each surface in the follow
 ing 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 graph as a subgraph. There is no
  4-color theorem of this type. In the talk these and related results will 
 be discussed.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR