Backbone colorings for graphs: Tree and path backbones

Broersma, Hajo and Fomin, Fedor V. and Golovach, Petr A. and Woeginger, Gerhard J. (2007) Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory, 55 (2). pp. 137-152. ISSN 0364-9024

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

Abstract:	We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$ ), a 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 two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of $G$ the number of colors needed for a backbone coloring of $G$ can roughly differ by a multiplicative factor of at most 2 from the chromatic number $\chi(G)$ ; for path backbones this factor is roughly ${3\over 2}$ . We show that the computational complexity of the problem "Given a graph $G$ , a spanning tree $T$ of $G$ , and an integer $\ell$ , is there a backbone coloring for $G$ and $T$ with at most $\ell$ colors?" jumps from polynomial to NP-complete between $\ell = 4$ (easy for all spanning trees) and $\ell = 5$ (difficult even for spanning paths). We finish the paper by discussing some open problems.
Item Type:	Article
Copyright:	© 2007 Wiley InterScience
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/61764
Official URL:	http://dx.doi.org/10.1002/jgt.20228
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 241718