(Circular) backbone colouring: tree backbones in planar graphs

Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8152, INRIA. 2012
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00759044
Contributeur : Frederic Havet <>
Soumis le : jeudi 29 novembre 2012 - 19:01:43
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : samedi 17 décembre 2016 - 18:35:08

Fichier

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

Identifiants

  • HAL Id : hal-00759044, version 1

Citation

Frédéric Havet, Andrew King, Mathieu Liedloff, Ioan Todinca. (Circular) backbone colouring: tree backbones in planar graphs. [Research Report] RR-8152, INRIA. 2012. 〈hal-00759044〉

Partager

Métriques

Consultations de la notice

605

Téléchargements de fichiers

189