# Noon lecture

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

On 19.11.2009 at 12:20 in corridor on the 2nd floor, there is the following noon lecture:

# Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs

## Luke Postle

## Georgia Tech

## Abstract

(Joint work with A. Asadi and R. Thomas)

Grotzsch's Theorem states that every triangle-free planar graph is 3-colorable. Thomassen conjectured that every triangle-free planar graph has exponentially many distinct 3-colorings. He proved that it has at least 2^{n^{1/12}/20000} distinct 3-colorings where n is the number of vertices. We show that it has at least 2^{\sqrt{n/600}} distinct 3-colorings.

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

Webmaster: kamweb.mff.cuni.cz Archive page