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

Fingerprint

Backbone
Colouring
Spanning tree
Path
Vertex Coloring
Split Graph
Spanning Subgraph
Graph in graph theory
Chromatic number
Multiplicative
Computational Complexity
Jump
Adjacent
NP-complete problem
Polynomial
Integer

Keywords

  • METIS-213360

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
Broersma, Haitze J. ; Fomin, F.V. ; Golovach, Petr ; Woeginger, Gerhard. / Backbone colorings for networks. Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers. editor / H.L. Bodlaender. Springer, 2003. pp. 131-142
@inproceedings{a81eb8213e494ab39d7b22fb56583bc6,
title = "Backbone colorings for networks",
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).",
keywords = "METIS-213360",
author = "Broersma, {Haitze J.} and F.V. Fomin and Petr Golovach and Gerhard Woeginger",
year = "2003",
doi = "10.1007/978-3-540-39890-5_12",
language = "English",
isbn = "978-3-540-20452-7",
publisher = "Springer",
pages = "131--142",
editor = "H.L. Bodlaender",
booktitle = "Graph-Theoretic Concepts in Computer Science",

}

Broersma, HJ, Fomin, FV, Golovach, P & Woeginger, G 2003, Backbone colorings for networks. in HL Bodlaender (ed.), 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.

Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers. ed. / H.L. Bodlaender. Springer, 2003. p. 131-142.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 -

Broersma HJ, Fomin FV, Golovach P, Woeginger G. Backbone colorings for networks. In Bodlaender HL, editor, Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers. Springer. 2003. p. 131-142 https://doi.org/10.1007/978-3-540-39890-5_12