Backbone colorings for networks: tree and path backbones
Hajo J. Broersma, Fedor V. Fomin, Petr A. Golovach, Gerhard J. Woeginger · University of Twente Research Information · 2003
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\\rightarrow \\{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.