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

In this paper we introduce the notion of I -colouring pound of a graph G: For given subsets I (v) pound of neighbours of v, for every vaV (G), this is a proper colouring of the vertices of G such that, in addition, vertices that appear together in some I (v) pound 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 for graphs embeddable in a fixed surface, 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 edge-colouring 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 embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree Delta embeddable in some fixed surface is at most plus a constant.