Skip to main content

Research Repository

Advanced Search

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

Broersma, H.J.; Marchal, L.; Paulusma, D.; Salman, A.N.M.

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number Thumbnail


Authors

H.J. Broersma

L. Marchal

A.N.M. Salman



Abstract

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 l-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 l. 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 l) 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.

Citation

Broersma, H., Marchal, L., Paulusma, D., & Salman, A. (2009). Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae. Graph Theory, 29(1), 143-162. https://doi.org/10.7151/dmgt.1437

Journal Article Type Article
Publication Date Mar 1, 2009
Deposit Date Sep 9, 2009
Publicly Available Date Mar 28, 2024
Journal Discussiones mathematicae. Graph theory.
Print ISSN 1234-3099
Publisher De Gruyter Open
Peer Reviewed Peer Reviewed
Volume 29
Issue 1
Pages 143-162
DOI https://doi.org/10.7151/dmgt.1437
Keywords Backbone coloring, Split graph, Matching, Star
Public URL https://durham-repository.worktribe.com/output/1527356
Publisher URL http://www.discuss.wmie.uz.zgora.pl//gt/29_1/gt29-561.htm

Files





You might also like



Downloadable Citations