(Circular) backbone colouring: tree backbones in planar graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

(Circular) backbone colouring: tree backbones in planar graphs

Résumé

Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., 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 BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.
On considère un graphe G (non-orienté) et un sous-graphe H de G. Le nombre chromatique q-dorsal BBCq(G,H) est le plus petit entier k tel que G puisse être coloré proprement avec les couleurs {1, ...,k} de telle sorte qu'en plus pour toute arête de H, les couleurs de ses deux extrémités diff'erent d'au moins q. Dans ce rapport, nous étudions le cas où G est planaire et H est une forêt. Nous donnons une série de résultats de NP-complétude ainsi que des bornes supérieures pour BBCq(G,H), suivant le type de forêt (couplage, galaxie, arbre couvrant). Nous abordons également une version circulaire du problème.
Fichier principal
Vignette du fichier
RR-8152.pdf (330.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00759044 , version 1 (29-11-2012)

Identifiants

  • HAL Id : hal-00759044 , version 1

Citer

Frédéric Havet, Andrew D. King, Mathieu Liedloff, Ioan Todinca. (Circular) backbone colouring: tree backbones in planar graphs. [Research Report] RR-8152, INRIA. 2012. ⟨hal-00759044⟩
415 Consultations
168 Téléchargements

Partager

Gmail Facebook X LinkedIn More