Backbone colorings along perfect matchings
Broersma, H.J. and Fujisawa, J. and Yoshimoto, K. (2003) Backbone colorings along perfect matchings. [Report]

PDF
201kB 
Abstract:  Given a graph and a spanning subgraph of (the backbone of ), a backbone coloring for and is a proper vertex coloring of in which the colors assigned to adjacent vertices in differ by at least two. In a recent paper, backbone colorings were introduced and studied in cases were the backbone is either a spanning tree or a spanning path. Here we study the case where the backbone is a perfect matching. We show that for perfect matching backbones of the number of colors needed for a backbone coloring of can roughly differ by a multiplicative factor of at most from the chromatic number . We show that the computational complexity of the problem ``Given a graph with a perfect matching , and an integer , is there a backbone coloring for and with at most colors?'' jumps from polynomial to NPcomplete between and . Finally, we consider the case where is a planar graph. 
Item Type:  Report 
Additional information:  Imported from MEMORANDA 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65891 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page