Name
Abstract | ||
|---|---|---|
Given an integer λ≥2, a graph G=(V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring of (G,H) is a proper vertex coloring V→{1,2,…} of G, in which the colors assigned to adjacent vertices in H differ by at least λ. We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone S of G the minimum number ℓ for which a λ-backbone coloring of (G,S) with colors in {1,…,ℓ} exists can roughly differ by a multiplicative factor of at most 2−1λ from the chromatic number χ(G). For the special case of matching backbones this factor is roughly 2−2λ+1. We also show that the computational complexity of the problem “Given a graph G with a star backbone S, and an integer ℓ, is there a λ-backbone coloring of (G,S) with colors in {1,…,ℓ}?” jumps from polynomially solvable to NP-complete between ℓ=λ+1 and ℓ=λ+2 (the case ℓ=λ+2 is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.04.007 | Discrete Mathematics |
Keywords | DocType | Volume |
λ-backbone coloring,λ-backbone coloring number,Star,Matching | Journal | 309 |
Issue | ISSN | Citations |
18 | 0012-365X | 1 |
PageRank | References | Authors |
0.36 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. J. Broersma | 1 | 266 | 33.68 |
| Jun Fujisawa | 2 | 9 | 1.94 |
| L. Marchal | 3 | 87 | 7.73 |
| Daniël Paulusma | 4 | 712 | 78.49 |
| A. N. M. Salman | 5 | 32 | 9.81 |
| Kiyoshi Yoshimoto | 6 | 133 | 22.65 |