λ-backbone colorings along pairwise disjoint stars and matchings

Broersma, H.J. and Fujisawa, J. and Marchal, L. and Paulusma, D. and Salman, A.N.M. and Yoshimoto, K. (2009) λ-backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics, 309 (18). pp. 5596-5609. ISSN 0012-365X

PDF
Restricted to UT campus only: Request a copy
1095Kb

Abstract:	Given an integer $\lambda \ge 2$ , a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$ ), a $\lambda$ -backbone coloring of $(G,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$ . We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone $S$ of $G$ the minimum number $\ell$ for which a $\lambda$ -backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$ exists can roughly differ by a multiplicative factor of at most $2-{1\over \lambda}$ from the chromatic number $\chi(G)$ . For the special case of matching backbones this factor is roughly $2-{2\over\lambda +1}$ . We also show that the computational complexity of the problem “Given a graph $G$ with a star backbone $S$ , and an integer $\ell$ , is there a $\lambda$ -backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$ ?” jumps from polynomially solvable to NP-complete between $\ell=\lambda+1$ and $\ell =\lambda+2$ (the case $\ell=\lambda+2$ is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.
Item Type:	Article
Copyright:	© 2009 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/68649
Official URL:	http://dx.doi.org/10.1016/j.disc.2008.04.007
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page