Geodesic
Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 1, pp. 143-162

Voir la notice de l'article provenant de la source Library of Science

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 λ-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 λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome of earlier studies is that the minimum number l of colors, for which such colorings V→ 1,2,...,l exist, in the worst case is a factor times the chromatic number (for path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, l is at most a small additive constant (depending on λ) higher than the chromatic number. 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.
Keywords: backbone coloring, split graph, matching, star 
@article{DMGT_2009_29_1_a8,
     author = {Broersma, Hajo and Marchal, Bert and Paulusma, Daniel and Salman, A.},
     title = {Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {143--162},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a8/}
}
TY  - JOUR
AU  - Broersma, Hajo
AU  - Marchal, Bert
AU  - Paulusma, Daniel
AU  - Salman, A.
TI  - Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 143
EP  - 162
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a8/
LA  - en
ID  - DMGT_2009_29_1_a8
ER  - 
%0 Journal Article
%A Broersma, Hajo
%A Marchal, Bert
%A Paulusma, Daniel
%A Salman, A.
%T Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 143-162
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a8/
%G en
%F DMGT_2009_29_1_a8
Broersma, Hajo; Marchal, Bert; Paulusma, Daniel; Salman, A. Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 1, pp. 143-162. http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a8/