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

Hajo Broersma; Bert Marchal; Daniel Paulusma; A.N.M. Salman

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 1, page 143-162
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHajo Broersma, et al. "Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number." Discussiones Mathematicae Graph Theory 29.1 (2009): 143-162. <http://eudml.org/doc/270641>.

@article{HajoBroersma2009,

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 λ-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.},

author = {Hajo Broersma, Bert Marchal, Daniel Paulusma, A.N.M. Salman},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {backbone coloring; split graph; matching; star},

language = {eng},

number = {1},

pages = {143-162},

title = {Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number},

url = {http://eudml.org/doc/270641},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Hajo Broersma

AU - Bert Marchal

AU - Daniel Paulusma

AU - A.N.M. Salman

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

VL - 29

IS - 1

SP - 143

EP - 162

AB - 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.

LA - eng

KW - backbone coloring; split graph; matching; star

UR - http://eudml.org/doc/270641

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
- [2] H.J. Broersma, A general framework for coloring problems: old results, new results and open problems, in: Proceedings of IJCCGGT 2003, LNCS 3330 (2005) 65-79. Zbl1117.05038
- [3] H.J. Broersma, F.V. Fomin, P.A. Golovach and G.J. Woeginger, Backbone colorings for networks, in: Proceedings of WG 2003, LNCS 2880 (2003) 131-142. Zbl1255.05076
- [4] H.J. Broersma, F.V. Fomin, P.A. Golovach and G.J. Woeginger, Backbone colorings for graphs: tree and path backbones, J. Graph Theory 55 (2007) 137-152, doi: 10.1002/jgt.20228. Zbl1118.05031
- [5] H.J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A.N.M. Salman and K. Yoshimoto, λ-Backbone colorings along pairwise disjoint stars and matchings, preprint (2004). www.durham.ac.uk/daniel.paulusma/Publications/Papers/Submitted/backbone.pdf. Zbl1213.05068
- [6] H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman, Improved upper bounds for λ-backbone colorings along matchings and stars, in: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2007, LNCS 4362 (2007) 188-199. Zbl1131.05301
- [7] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
- [8] P.L. Hammer and S. Földes, Split graphs, Congr. Numer. 19 (1977) 311-315.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.