8494 articles  [version française]

hal-00758548, version 1

Backbone colouring: tree backbones with small diameter in planar graphs

Victor Campos () a, 1, Frederic Havet () 2, Rudini Sampaio () 1, Ana Silva 1

N° RR-8151 (2012)

Abstract: Given a graph $G$ and a spanning subgraph $T$ of $G$, a {\it backbone $k$-colouring} for $(G,T)$ is a mapping $c:V(G)\to\{1,\ldots,k\}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$. The {\it backbone chromatic number} $BBC(G,T)$ is the smallest integer $k$ such that there exists a backbone $k$-colouring of $(G,T)$. In 2007, Broersma et al. \cite{BFG+07} conjectured that $BBC(G,T)\leq 6$ for every planar graph $G$ and every spanning tree $T$ of $G$. In this paper, we prove this conjecture when $T$ has diameter at most four.

  • a –  Universidade Federal do Ceara
  • 1:  Parallelism, Graphs and Optimization Research Group (ParGO)
  • Universidade Federal do Ceara
  • 2:  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • Domain : Computer Science/Discrete Mathematics
  • Internal note : RR-8151
 
  • hal-00758548, version 1
  • http://hal.inria.fr/hal-00758548
  • oai:hal.inria.fr:hal-00758548
  • From: Frederic Havet <>
  • Submitted on: Wednesday, 28 November 2012 18:45:35
  • Updated on: Thursday, 29 November 2012 13:49:05