Maps & Graphs on Surfaces

Duration: 59 mins 49 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1082/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Carsten Thomassen (Technical University of Denmark) Monday 2 June 2008, 17:00-18:00

Created:

2008-06-11 08:16

Collection:

Rothschild Seminars

Publisher:

Isaac Newton Institute

Carsten Thomassen

Language:

eng (English)

Credits:

Author:	Carsten Thomassen
Producer:	Steve Greenham


Abstract:	Graph coloring is a extensively studied subject, partly because 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 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 graph as a subgraph. There is no 4-color theorem of this type. In the talk these and related results will be discussed. Original web seminar at: http://www.newton.ac.uk/programmes/CSM/seminars/060217001.html In association with the Newton Combinatorics and Statistical Mechanics programme: http://www.newton.ac.uk/programmes/CSM/index.html

Abstract:

Graph coloring is a extensively studied subject, partly because 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 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 graph as a subgraph. There is no 4-color theorem of this type. In the talk these and related results will be discussed.

Original web seminar at: http://www.newton.ac.uk/programmes/CSM/seminars/060217001.html
In association with the Newton Combinatorics and Statistical Mechanics programme: http://www.newton.ac.uk/programmes/CSM/index.html

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	480x360	1.84 Mbits/sec	827.59 MB	View	Download
WebM	480x360	620.93 kbits/sec	271.81 MB	View	Download
Flash Video	480x360	567.95 kbits/sec	248.83 MB	View	Download
iPod Video	480x360	505.45 kbits/sec	221.45 MB	View	Download
QuickTime (for download)	384x288	849.18 kbits/sec	372.04 MB	View	Download
QuickTime (for streaming)	480x360	906.4 kbits/sec	397.10 MB	View	Download
MP3	44100 Hz	125.0 kbits/sec	54.58 MB	Listen	Download
Windows Media Video (for download)		477.71 kbits/sec	209.29 MB	View	Download
Windows Media Video (for streaming)		448.56 kbits/sec	196.52 MB	View	Download	Stream
Auto *	(Allows browser to choose a format it supports)