On backbone coloring of graphs |
| |
Authors: | Weifan Wang Yuehua Bu Micka?l Montassier André Raspaud |
| |
Affiliation: | 1. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China 2. LaBRI UMR CNRS 5800, Universite Bordeaux I, 33405, Talence Cedex, France
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|