A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

Details A Unified Approach to Distance-Two Colouring of Graphs on Surfaces A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

2008-12-07

arxiv.org/abs/0812.1345v3

Mathematics

Combinatorics

36 pages

Scientific paper

In this paper we introduce the notion of $\Sigma$-colouring of a graph $G$: For given subsets $\Sigma(v)$ of neighbours of $v$, for every $v\in V(G)$, this is a proper colouring of the vertices of $G$ such that, in addition, vertices that appear together in some $\Sigma(v)$ 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 $\frac32\,\Delta$ plus a constant.

Affiliated with

Also associated with

No associations

Rating

A Unified Approach to Distance-Two Colouring of Graphs on Surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Unified Approach to Distance-Two Colouring of Graphs on Surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Unified Approach to Distance-Two Colouring of Graphs on Surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-450022