λλ-backbone colorings along pairwise disjoint stars and matchings

Given an integer λ≥2λ≥2, a graph G=(V,E)G=(V,E) and a spanning subgraph HH of GG (the backbone of GG), a λλ-backbone coloring of (G,H)(G,H) is a proper vertex coloring V→{1,2,…}V→{1,2,…} of GG, in which the colors assigned to adjacent vertices in HH 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 SS of GG the minimum number ℓℓ for which a λλ-backbone coloring of (G,S)(G,S) with colors in {1,…,ℓ}{1,…,ℓ} exists can roughly differ by a multiplicative factor of at most 2−1λ from the chromatic number χ(G)χ(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 GG with a star backbone SS, and an integer ℓℓ, is there a λλ-backbone coloring of (G,S)(G,S) with colors in {1,…,ℓ}{1,…,ℓ}?” jumps from polynomially solvable to NP-complete between ℓ=λ+1ℓ=λ+1 and ℓ=λ+2ℓ=λ+2 (the case ℓ=λ+2ℓ=λ+2 is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.