On backbone coloring of graphs

On backbone coloring of graphs

0.00 Avg rating0 Votes
Article ID: iaor2012239
Volume: 23
Issue: 1
Start Page Number: 79
End Page Number: 93
Publication Date: Jan 2012
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: combinatorial optimization
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 uvE(H) and |f(u)-f(v)|≥1 if uvE(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=TC 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.

Reviews

Required fields are marked *. Your email address will not be published.