# 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 157Kb |

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