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

Broersma, H.J. and Marchal, L. and Paulusma, D. and Salman, A.N.M. (2009) *Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number.* Discussiones Mathematicae Graph Theory, 29 (1). pp. 143-162. ISSN 1234-3099

HTML Restricted to UT campus only: Request a copy 4Kb |

Abstract: | We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph and a spanning subgraph of (the backbone of ), a -backbone coloring for and is a proper vertex coloring of in which the colors assigned to adjacent vertices in 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 of colors, for which such colorings 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, 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 than the previously known bounds. |

Item Type: | Article |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/67842 |

Official URL: | http://www.discuss.wmie.uz.zgora.pl//gt/29_1/gt29-561.htm |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page