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

Share/Save/Bookmark

Broersma, Hajo and Marchal, Bert and Paulusma, Daniël 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

open access
[img]
Preview
PDF - Published Version
163kB
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 $\gamma$-backbone coloring for $G$ and $H$ is a proper vertex coloring $V\to \{1,2,\ldots\}$ of $G$ in which the colors assigned to adjacent vertices in $H$ differ by at least $\gamma$. 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 $\ell$ of colors, for which such colorings $V\to \{1,2,\ldots, \ell\}$ 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, $\ell$ is at most a small additive constant (depending on $\gamma$) 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 $\ell$ 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://dx.doi.org/10.7151/dmgt.1437
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page