Backbone colorings for graphs : tree and path backbones

H.J. Broersma, F.V. Fomin, P.A. Golovach, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

28 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 {1,2,} 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 (G); for path backbones this factor is roughly . We show that the computational complexity of the problem Given a graph G, a spanning tree T of G, and an integer , is there a backbone coloring for G and T with at most colors? jumps from polynomial to NP-complete between = 4 (easy for all spanning trees) and = 5 (difficult even for spanning paths). We finish the paper by discussing some open problems.
Original languageEnglish
Pages (from-to)137-152
JournalJournal of Graph Theory
Issue number2
Publication statusPublished - 2007


Dive into the research topics of 'Backbone colorings for graphs : tree and path backbones'. Together they form a unique fingerprint.

Cite this