8739 articles  [version française]

hal-00759044, version 1

(Circular) backbone colouring: tree backbones in planar graphs

Frederic Havet () 1, Andrew D. King 23, Mathieu Liedloff () 4, Ioan Todinca () 4

N° RR-8152 (2012)

Abstract: Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H is a forest. We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.

  • 1:  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis (UNS) – CNRS : UMR7271
  • 2:  Department of Mathematics
  • Simon Fraser University
  • 3:  Department of computer science [Burnaby]
  • Simon Fraser University
  • 4:  Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
  • Université d'Orléans : EA4022 – Ecole Nationale Supérieure d'Ingénieurs de Bourges
  • Domain : Computer Science/Discrete Mathematics
  • Internal note : RR-8152
  • hal-00759044, version 1
  • oai:hal.inria.fr:hal-00759044
  • From: 
  • Submitted on: Thursday, 29 November 2012 19:01:43
  • Updated on: Friday, 30 November 2012 11:23:55