CDAM: Computational, Discrete and Applicable Mathematics@LSE 

CDAM Research Report, LSECDAM200823December 2008 
A Unified Approach to DistanceTwo Colouring of Graphs on Surfaces
Omid Amini, Louis Esperet, and Jan van den Heuvel
In this paper we introduce the notion of (A,B)colouring of a graph: For given vertex sets A,B, this is a colouring of the vertices in B so that both adjacent vertices and vertices with a common neighbour in A receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result which implies asymptotic versions of Wegner's and Borodin's Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edgecolouring of multigraphs and then use Kahn's result that the list chromatic index is close to 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 Δ embeddable in some fixed surface is at most 3Δ⁄2 plus a constant.
A PDF file (446 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200823, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7494. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 