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