On backbone coloring of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Combinatorial Optimization Year : 2012

On backbone coloring of graphs


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.

Dates and versions

lirmm-00782811 , version 1 (30-01-2013)



Yuehua Bu, Mickaël Montassier, André Raspaud, Weifan Wang. On backbone coloring of graphs. Journal of Combinatorial Optimization, 2012, 23, pp.79-93. ⟨10.1007/s10878-010-9342-6⟩. ⟨lirmm-00782811⟩
166 View
0 Download



Gmail Mastodon Facebook X LinkedIn More