Premium
Backbone colorings for graphs: Tree and path backbones
Author(s) -
Broersma Hajo,
Fomin Fedor V.,
Golovach Petr A.,
Woeginger Gerhard J.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20228
Subject(s) - combinatorics , spanning tree , mathematics , minimum degree spanning tree , complete coloring , shortest path tree , fractional coloring , multiplicative function , edge coloring , vertex (graph theory) , discrete mathematics , graph , graph power , line graph , mathematical analysis
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 ${{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 ℓ, 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. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 137–152, 2007