{
  "id": "0812.1345",
  "version": "v4",
  "published": "2008-12-07T13:38:29.000Z",
  "updated": "2012-05-06T16:23:30.000Z",
  "title": "A Unified Approach to Distance-Two Colouring of Graphs on Surfaces",
  "authors": [
    "Omid Amini",
    "Louis Esperet",
    "Jan van den Heuvel"
  ],
  "comment": "36 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2012-05-06T16:23:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C10"
    ],
    "keywords": [
      "unified approach",
      "distance-two colouring",
      "fixed surface",
      "implies asymptotic versions",
      "list chromatic index"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0812.1345A"
    }
  }
}