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 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Pour un graphe $G$ et un sous-graphe $T$ de $G$, une {\it $k$-coloration dorsale} de $(G,T)$ est une application $c:V(G)\to\{1,\ldots,k\}$ telle que $|c(u)-c(v)|\geq 2$ pour tout arête $uv\in E(T)$ et $|c(u)-c(v)|\geq 1$ pour toute arête $uv\in E(G)\setminus E(T)$. Le {\it nombre chromatique dorsal} $BBC(G,T)$ est le plus petit entier $k$ tel qu'il existe une $k$-coloration dorsale de $(G,T)$. En 2007, Broersma et al. \cite{BFG+07} ont conjecturé que $BBC(G,T)\leq 6$ pour tout graphe planaire $G$ et tout arbre couvrant $T$ de $G$. Dans ce rapport, nous montrons cette conjecture lorsque $T$ est de diamétre au plus 4.
Type de document :
Rapport
[Research Report] RR-8151, INRIA. 2012
Liste complète des métadonnées


https://hal.inria.fr/hal-00758548
Contributeur : Frederic Havet <>
Soumis le : mercredi 28 novembre 2012 - 18:45:35
Dernière modification le : samedi 17 septembre 2016 - 01:35:29
Document(s) archivé(s) le : samedi 17 décembre 2016 - 17:28:37

Fichier

RR-8151.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00758548, version 1

Collections

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>

Partager

Métriques

Consultations de
la notice

582

Téléchargements du document

823