Backbone colouring: Tree backbones with small diameter in planar graphs

Victor Campos 1 Frédéric Havet 2 Rudini Sampaio 1 Ana Silva 1
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Given a graph $G$ and a spanning subgraph $T$ of $G$, a backbone $k$-coloring 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 backbone chromatic number $\chi_{bb}(G,T)$ is the smallest integer $k$ such that there exists a backbone $k$-coloring of $(G,T)$. In 2007, Broersma et al. \cite{BFG+07} conjectured that $\chi_{bb}(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.
Type de document :
Article dans une revue
Liste complète des métadonnées


https://hal.inria.fr/hal-00821608
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:09:07
Dernière modification le : mardi 25 octobre 2016 - 01:05:07

Fichier

BBCdiam2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Victor Campos, Frédéric Havet, Rudini Sampaio, Ana Silva. Backbone colouring: Tree backbones with small diameter in planar graphs. Theoretical Computer Science, Elsevier, 2013, 487, pp.50-64. <http://www.sciencedirect.com/science/article/pii/S0304397513001941>. <10.1016/j.tcs.2013.03.003>. <hal-00821608>

Partager

Métriques

Consultations de
la notice

413

Téléchargements du document

91