On backbone coloring of graphs

Abstract : Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,...,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum average degree, graphs with maximum degree 3, etc.
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2012, 23, pp.79-93. 〈10.1007/s10878-010-9342-6〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00782811
Contributeur : Mickael Montassier <>
Soumis le : mercredi 30 janvier 2013 - 16:18:05
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

Yuehua Bu, Mickaël Montassier, André Raspaud, Weifan Wang. On backbone coloring of graphs. Journal of Combinatorial Optimization, Springer Verlag, 2012, 23, pp.79-93. 〈10.1007/s10878-010-9342-6〉. 〈lirmm-00782811〉

Partager

Métriques

Consultations de la notice

195