## Abstract

We study backbone colorings, a variation on classical vertex colorings: Given a graph G=(V,E) and a spanning subgraph H (the backbone) of G, a backbone coloring for G and H is a proper vertex coloring V →{ 1,2,... } in which the colors assigned to adjacent vertices in H differ by at least two. We concentrate on the cases where the backbone is either a spanning tree or a spanning path.

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 32 . In the special case of split graphs G, the difference from χ(G) is at most an additive constant 2 or 1, for tree backbones and path backbones, respectively. The computational complexity of the problem ‘Given a graph G, a spanning tree T of G, and an integer l, is there a backbone coloring for G and T with at most l colors?’ jumps from polynomial to NP-complete between l = 4 (easy for all spanning trees) and l = 5 (difficult even for spanning paths).

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 32 . In the special case of split graphs G, the difference from χ(G) is at most an additive constant 2 or 1, for tree backbones and path backbones, respectively. The computational complexity of the problem ‘Given a graph G, a spanning tree T of G, and an integer l, is there a backbone coloring for G and T with at most l colors?’ jumps from polynomial to NP-complete between l = 4 (easy for all spanning trees) and l = 5 (difficult even for spanning paths).

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers |

Editors | H.L. Bodlaender |

Publisher | Springer |

Pages | 131-142 |

ISBN (Electronic) | 978-3-540-39890-5 |

ISBN (Print) | 978-3-540-20452-7 |

DOIs | |

Publication status | Published - 2003 |

### Publication series

Name | |
---|---|

Volume | 2880 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- METIS-213360