### Abstract

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 |

### Fingerprint

### Keywords

- METIS-213360

### Cite this

*Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers*(pp. 131-142). Springer. https://doi.org/10.1007/978-3-540-39890-5_12

}

*Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers.*Springer, pp. 131-142. https://doi.org/10.1007/978-3-540-39890-5_12

**Backbone colorings for networks.** / Broersma, Haitze J.; Fomin, F.V.; Golovach, Petr; Woeginger, Gerhard.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Backbone colorings for networks

AU - Broersma, Haitze J.

AU - Fomin, F.V.

AU - Golovach, Petr

AU - Woeginger, Gerhard

PY - 2003

Y1 - 2003

N2 - 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).

AB - 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).

KW - METIS-213360

U2 - 10.1007/978-3-540-39890-5_12

DO - 10.1007/978-3-540-39890-5_12

M3 - Conference contribution

SN - 978-3-540-20452-7

SP - 131

EP - 142

BT - Graph-Theoretic Concepts in Computer Science

A2 - Bodlaender, H.L.

PB - Springer

ER -