Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Improved upper bounds for $\lambda$-backbone colorings along matchings and stars


Share/Save/Bookmark

Broersma, H.J. and Marchal, L. and Paulusma, D. and Salman, A.N.M. (2007) Improved upper bounds for $\lambda$-backbone colorings along matchings and stars. In: Proceedings of SOFSEM 2007: Theory and Practice of Computer Science, 20-26 Jan 2007, Harrachov, Czech Republic.

[img]PDF
Restricted to UT campus only: Request a copy
404Kb
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.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/61929
Official URL:http://dx.doi.org/10.1007/978-3-540-69507-3_15
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 241921