# Backbone colouring: tree backbones with small diameter in planar graphs

2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Document type :
Reports

Cited literature [8 references]

https://hal.inria.fr/hal-00758548
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Wednesday, November 28, 2012 - 6:45:35 PM
Last modification on : Saturday, June 25, 2022 - 11:08:59 PM
Long-term archiving on: : Saturday, December 17, 2016 - 5:28:37 PM

### File

RR-8151.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00758548, version 1

### Citation

Victor Campos, Frédéric Havet, Rudini Sampaio, Ana Silva. Backbone colouring: tree backbones with small diameter in planar graphs. [Research Report] RR-8151, INRIA. 2012. ⟨hal-00758548⟩

Record views