@inbook {IOPORT.05655929,
    author       = {Broersma, Hajo and Fomin, Fedor V. and Golovach, Petr A. and Woeginger, Gerhard J.},
    title        = {Backbone colorings for networks.},
    year         = {2003},
    booktitle    = {Graph-theoretic concepts in computer science. 29th international workshop, WG 2003, Elspeet, The Netherlands, June 19--21, 2003. Revised papers},
    isbn         = {3-540-20452-0},
    pages        = {131-142},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/b93953},
    abstract     = {Summary: We study backbone colorings, a variation on classical vertex colorings: Given a graph $G=(V,E)$ and a spanning subgraph $H$ (the backbone) of $G$, a backbone coloring for $G$ and $H$ is a proper vertex coloring $V\to\{1,2,\dots\}$ in which the colors assigned to adjacent vertices in $H$ differ by at least two. We concentrate on the cases where the backbone is either a spanning tree or a spanning path. 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 $\frac{3}{2}$. In the special case of split graphs $G$, the difference from $\chi(G)$ is at most an additive constant 2 or 1, for tree backbones and path backbones, respectively. 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).},
    identifier   = {05655929},
}