Backbone colorings for networks

Haitze J. Broersma, F.V. Fomin, Petr Golovach, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)

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).
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers
EditorsH.L. Bodlaender
PublisherSpringer
Pages131-142
ISBN (Electronic)978-3-540-39890-5
ISBN (Print)978-3-540-20452-7
DOIs
Publication statusPublished - 2003

Publication series

Name
Volume2880
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • METIS-213360

Fingerprint Dive into the research topics of 'Backbone colorings for networks'. Together they form a unique fingerprint.

  • Cite this

    Broersma, H. J., Fomin, F. V., Golovach, P., & Woeginger, G. (2003). Backbone colorings for networks. In H. L. Bodlaender (Ed.), 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