# (Circular) backbone colouring: forest backbones in planar graphs

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Consider an undirected graph $G$ and a subgraph $H$ of $G$, on the same vertex set. The {\it $q$-backbone chromatic number} $\BBC_q(G,H)$ is the minimum $k$ such that $G$ can be properly coloured with colours from $\{1, \dots, 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 $\BBC_q(G,H)$, depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, 169, pp.119-134. 〈10.1016/j.dam.2014.01.011〉

Littérature citée [14 références]

https://hal.inria.fr/hal-00957243
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 15:48:54
Dernière modification le : mardi 6 novembre 2018 - 01:17:28

### Fichier

complexity-backbone.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Frédéric Havet, Andrew D. King, Mathieu Liedloff, Ioan Todinca. (Circular) backbone colouring: forest backbones in planar graphs. Discrete Applied Mathematics, Elsevier, 2014, 169, pp.119-134. 〈10.1016/j.dam.2014.01.011〉. 〈hal-00957243〉

### Métriques

Consultations de la notice

## 424

Téléchargements de fichiers