Backbone colorings for graphs: Tree and path backbones

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.