# Improved upper bounds for λ-backbone colorings along matchings and stars

Haitze J. Broersma, L. Marchal, Daniël Paulusma, M. Salman

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

### 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 $\lambda$-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 $\lambda$. 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 all studied types of backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\lambda$) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. 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.
Original language Undefined Proceedings of SOFSEM 2007: Theory and Practice of Computer Science J. van Leeuwen, G.F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plásil Berlin Springer 188-199 12 978-3-540-69506-6 Published - 13 Jul 2007

### Publication series

Name Lecture Notes in Computer Science Springer Verlag LNCS4549 4362 0302-9743 1611-3349

• EWI-11097
• IR-61929
• METIS-241921

### Cite this

Broersma, H. J., Marchal, L., Paulusma, D., & Salman, M. (2007). Improved upper bounds for λ-backbone colorings along matchings and stars. In J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, & F. Plásil (Eds.), Proceedings of SOFSEM 2007: Theory and Practice of Computer Science (pp. 188-199). [10.1007/978-3-540-69507-3] (Lecture Notes in Computer Science; Vol. 4362, No. LNCS4549). Berlin: Springer. https://doi.org/10.1007/978-3-540-69507-3_15, https://doi.org/10.1007/978-3-540-69507-3