λ-backbone colorings along pairwise disjoint stars and matchings

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.