Backbone colorings of graphs with bounded degree

We study backbone colorings, a variation on classical vertex colorings: Given a graph GG and a subgraph HH of GG (the backbone of GG), a backbone coloring for GG and HH is a proper vertex kk-coloring of GG in which the colors assigned to adjacent vertices in HH differ by at least 22. The minimal k∈Nk∈N for which such a coloring exists is called the backbone chromatic number of GG. We show that for a graph GG of maximum degree ΔΔ where the backbone graph is a dd-degenerated subgraph of GG, the backbone chromatic number is at most Δ+d+1Δ+d+1 and moreover, in the case when the backbone graph being a matching we prove that the backbone chromatic number is at most Δ+1Δ+1. We also present examples where these bounds are attained.Finally, the asymptotic behavior of the backbone chromatic number is studied regarding the degrees of GG and HH. We prove for any sparse graph GG that if the maximum degree of a backbone graph is small compared to the maximum degree of GG, then the backbone chromatic number is at most Δ(G)−Δ(G).