Improved upper bounds for λ-backbone colorings along matchings and stars

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at, WG2003. Given a graph G = (V, E) and a spanning subgraph H of G (the backbone of G), a lambda-backbone coloring for G and 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 lambda. The main outcome of earlier studies is that the minimum number e of colors for which such colorings V -> {1, 2,...,l} I exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones,. e is at most a small additive constant (depending on lambda) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on l than the previously known bounds.