Backbone colorings for graphs: Tree and path backbones

Haitze J. Broersma, Fedor V. Fomin, Petr A. Golovach, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

26 Citations (Scopus)


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.
Original languageUndefined
Article number10.1002/jgt.20228
Pages (from-to)137-152
Number of pages16
JournalJournal of graph theory
Issue numberSINTEF A13/2
Publication statusPublished - Jan 2007


  • EWI-10334
  • IR-61764
  • METIS-241718

Cite this