On backbone coloring of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Optimization Année : 2012

On backbone coloring of graphs

Résumé

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 et versions

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

Identifiants

Citer

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⟩
164 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More