λ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. 55965609. ISSN 0012365X
PDF
Restricted to UT campus only : Request a copy 1MB 
Abstract:  Given an integer , a graph and a spanning subgraph of (the backbone of ), a backbone coloring of is a proper vertex coloring of , in which the colors assigned to adjacent vertices in differ by at least . 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 of the minimum number for which a backbone coloring of with colors in exists can roughly differ by a multiplicative factor of at most from the chromatic number . For the special case of matching backbones this factor is roughly . We also show that the computational complexity of the problem “Given a graph with a star backbone , and an integer , is there a backbone coloring of with colors in ?” jumps from polynomially solvable to NPcomplete between and (the case is even NPcomplete 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:  
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 
Repository Staff Only: item control page