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

作者：Amini Omid^*; Esperet Louis; Van den Heuvel Jan

来源：Combinatorica, 2013, 33(3): 253-296.

DOI：10.1007/s00493-013-2573-2

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%26apos;s and Borodin%26apos;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%26apos;s result that the list chromatic index is close to the fractional chromatic index. %26lt;br%26gt;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.

• 出版日期2013-6