# Backbone colorings for graphs: Tree and path backbones

Broersma, Hajo
and
Fomin, Fedor V.
and
Golovach, Petr A.
and
Woeginger, Gerhard J.
(2007)
*Backbone colorings for graphs: Tree and path backbones.*
Journal of Graph Theory, 55
(2).
pp. 137-152.
ISSN 0364-9024

PDF
Restricted to UT campus only : Request a copy 161kB |

Abstract: | We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph and a spanning subgraph of (the backbone of ), a backbone coloring for and is a proper vertex coloring of in which the colors assigned to adjacent vertices in 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 the number of colors needed for a backbone coloring of can roughly differ by a multiplicative factor of at most 2 from the chromatic number ; for path backbones this factor is roughly . We show that the computational complexity of the problem "Given a graph , a spanning tree of , and an integer , is there a backbone coloring for and with at most colors?" jumps from polynomial to NP-complete between (easy for all spanning trees) and (difficult even for spanning paths). We finish the paper by discussing some open problems. |

Item Type: | Article |

Copyright: | © 2007 Wiley InterScience |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/61764 |

Official URL: | http://dx.doi.org/10.1002/jgt.20228 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 241718