8739 articles  [version française]

hal-00759527, version 1

List circular backbone colouring

Frederic Havet () 12, Andrew D. King 34

N° RR-8159 (2012)

Abstract: A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the $q$-backbone colouring problem, these minimum distances are either $q$ or $1$, depending on whether or not the edge is in the {\em backbone}. In this paper we consider the list version of this problem, with particular focus on colours in $\Z_p$ -- this problem is closely related to the problem of circular choosability. We first prove that the {\em list circular $q$-backbone chromatic number} of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.

  • 1:  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis (UNS) – CNRS : UMR7271
  • 2:  Pacific Institute for the Mathematical Sciences (PIMS)
  • University of Calgary
  • 3:  Department of Mathematics
  • Simon Fraser University
  • 4:  Department of computer science [Burnaby]
  • Simon Fraser University
  • Domain : Computer Science/Discrete Mathematics
  • Internal note : RR-8159
  • hal-00759527, version 1
  • oai:hal.inria.fr:hal-00759527
  • From: 
  • Submitted on: Friday, 30 November 2012 19:22:30
  • Updated on: Monday, 3 December 2012 13:27:32