@inproceedings{ee2495ef4fd04e2f8541a35ceccc1df9,

title = "Improved upper bounds for λ-backbone colorings along matchings and stars",

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.",

keywords = "EWI-11097, IR-61929, METIS-241921",

author = "Broersma, {Haitze J.} and L. Marchal and Dani{\"e}l Paulusma and M. Salman",

note = "10.1007/978-3-540-69507-3 ",

year = "2007",

month = jul,

day = "13",

doi = "10.1007/978-3-540-69507-3_15",

language = "Undefined",

isbn = "978-3-540-69506-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "LNCS4549",

pages = "188--199",

editor = "{van Leeuwen}, J. and G.F. Italiano and {van der Hoek}, W. and C. Meinel and H. Sack and F. Pl{\'a}sil",

booktitle = "Proceedings of SOFSEM 2007: Theory and Practice of Computer Science",

}