Noon lecture

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

On 20.11.2008 at 12:20 in S8, there is the following noon lecture:

A unified approach to distance-two coloring of graphs on surfaces

Louis Esperet

Abstract

In this talk I will introduce the notion of (A,B)-coloring of a graph. For given vertex sets A, B, this is a coloring of the vertices in B so that both adjacent vertices in B and vertices with a common neighbor in A have distinct colors.This concept generalises the notion of coloring the square of a graph and of cyclic coloring of graphs embedded on a surface. We prove a general result which implies asymptotic versions of Wegner's and Borodin's Conjecture on the planar versions of these two colorings. Using a recent approach of Havet et al., we reduce the problem to edge-coloring of multigraphs and then use Kahn's result that the list chromatic index is close from the fractional chromatic index. Our results are based on a strong structural lemma for graphs embedded in a surface, which also implies that the size of a clique in the square of a graph of maximum degree D embeddable on a fixed 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