# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 10.11.2009 at 12:20 in corridor, there is the following noon lecture:

# Counterexample to the conjecture of Grunbaum

## Martin Kochol

## MU SAV, Bratislava

## Abstract

By a classical result of Tait, the four color theorem is equivalent with the statement that each 2-edge-connected 3-regular planar graph has a 3-edge-coloring. An embedding of a graph in a surface is called polyhedral if its dual has no multiple edges and loops. A conjecture of Grunbaum, presented in 1968, states that each 3-regular graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring. With respect to the result of Tait, it aims to generalize the four color theorem for any orientable surface. We present a negative solution of this conjecture, showing that for each orientable surface of genus at least 5, there exists a 3-regular non 3-edge-colorable graph with a polyhedral embedding in the surface.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010