Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Mickael Montassier <>
Submitted on : Wednesday, January 30, 2013 - 4:18:05 PM
Last modification on : Tuesday, August 18, 2020 - 4:46:07 PM

Links full text



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⟩



Record views