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

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 241718