λ-backbone colorings along pairwise disjoint stars and matchings

Haitze J. Broersma, J. Fujisawa, L. Marchal, Daniël Paulusma, M. Salman, K. Yoshimoto

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)
6 Downloads (Pure)

Abstract

Given an integer $\lambda \ge 2$, a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring of $(G,H)$ is a proper vertex coloring $V\to\{1,2,\ldots\}$ of $G$, in which the colors assigned to adjacent vertices in $H$ differ by at least $\lambda$. We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone $S$ of $G$ the minimum number $\ell$ for which a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$ exists can roughly differ by a multiplicative factor of at most $2-{1\over \lambda}$ from the chromatic number $\chi(G)$. For the special case of matching backbones this factor is roughly $2-{2\over\lambda +1}$. We also show that the computational complexity of the problem “Given a graph $G$ with a star backbone $S$, and an integer $\ell$, is there a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$?��? jumps from polynomially solvable to NP-complete between $\ell=\lambda+1$ and $\ell =\lambda+2$ (the case $\ell=\lambda+2$ is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.
Original languageUndefined
Pages (from-to)5596-5609
Number of pages14
JournalDiscrete mathematics
Volume309
Issue number18
DOIs
Publication statusPublished - 28 Sep 2009

Cite this

Broersma, H. J., Fujisawa, J., Marchal, L., Paulusma, D., Salman, M., & Yoshimoto, K. (2009). λ-backbone colorings along pairwise disjoint stars and matchings. Discrete mathematics, 309(18), 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007
Broersma, Haitze J. ; Fujisawa, J. ; Marchal, L. ; Paulusma, Daniël ; Salman, M. ; Yoshimoto, K. / λ-backbone colorings along pairwise disjoint stars and matchings. In: Discrete mathematics. 2009 ; Vol. 309, No. 18. pp. 5596-5609.
@article{3418dd35137f4cf792274e8e0b2c3c65,
title = "λ-backbone colorings along pairwise disjoint stars and matchings",
abstract = "Given an integer $\lambda \ge 2$, a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring of $(G,H)$ is a proper vertex coloring $V\to\{1,2,\ldots\}$ of $G$, in which the colors assigned to adjacent vertices in $H$ differ by at least $\lambda$. We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone $S$ of $G$ the minimum number $\ell$ for which a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$ exists can roughly differ by a multiplicative factor of at most $2-{1\over \lambda}$ from the chromatic number $\chi(G)$. For the special case of matching backbones this factor is roughly $2-{2\over\lambda +1}$. We also show that the computational complexity of the problem “Given a graph $G$ with a star backbone $S$, and an integer $\ell$, is there a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$?��? jumps from polynomially solvable to NP-complete between $\ell=\lambda+1$ and $\ell =\lambda+2$ (the case $\ell=\lambda+2$ is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.",
author = "Broersma, {Haitze J.} and J. Fujisawa and L. Marchal and Dani{\"e}l Paulusma and M. Salman and K. Yoshimoto",
year = "2009",
month = "9",
day = "28",
doi = "10.1016/j.disc.2008.04.007",
language = "Undefined",
volume = "309",
pages = "5596--5609",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "18",

}

Broersma, HJ, Fujisawa, J, Marchal, L, Paulusma, D, Salman, M & Yoshimoto, K 2009, 'λ-backbone colorings along pairwise disjoint stars and matchings' Discrete mathematics, vol. 309, no. 18, pp. 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007

λ-backbone colorings along pairwise disjoint stars and matchings. / Broersma, Haitze J.; Fujisawa, J.; Marchal, L.; Paulusma, Daniël; Salman, M.; Yoshimoto, K.

In: Discrete mathematics, Vol. 309, No. 18, 28.09.2009, p. 5596-5609.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - λ-backbone colorings along pairwise disjoint stars and matchings

AU - Broersma, Haitze J.

AU - Fujisawa, J.

AU - Marchal, L.

AU - Paulusma, Daniël

AU - Salman, M.

AU - Yoshimoto, K.

PY - 2009/9/28

Y1 - 2009/9/28

N2 - Given an integer $\lambda \ge 2$, a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring of $(G,H)$ is a proper vertex coloring $V\to\{1,2,\ldots\}$ of $G$, in which the colors assigned to adjacent vertices in $H$ differ by at least $\lambda$. We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone $S$ of $G$ the minimum number $\ell$ for which a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$ exists can roughly differ by a multiplicative factor of at most $2-{1\over \lambda}$ from the chromatic number $\chi(G)$. For the special case of matching backbones this factor is roughly $2-{2\over\lambda +1}$. We also show that the computational complexity of the problem “Given a graph $G$ with a star backbone $S$, and an integer $\ell$, is there a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$?��? jumps from polynomially solvable to NP-complete between $\ell=\lambda+1$ and $\ell =\lambda+2$ (the case $\ell=\lambda+2$ is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.

AB - Given an integer $\lambda \ge 2$, a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring of $(G,H)$ is a proper vertex coloring $V\to\{1,2,\ldots\}$ of $G$, in which the colors assigned to adjacent vertices in $H$ differ by at least $\lambda$. We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone $S$ of $G$ the minimum number $\ell$ for which a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$ exists can roughly differ by a multiplicative factor of at most $2-{1\over \lambda}$ from the chromatic number $\chi(G)$. For the special case of matching backbones this factor is roughly $2-{2\over\lambda +1}$. We also show that the computational complexity of the problem “Given a graph $G$ with a star backbone $S$, and an integer $\ell$, is there a $\lambda$-backbone coloring of $(G,S)$ with colors in $\{1,\ldots,\ell\}$?��? jumps from polynomially solvable to NP-complete between $\ell=\lambda+1$ and $\ell =\lambda+2$ (the case $\ell=\lambda+2$ is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.

U2 - 10.1016/j.disc.2008.04.007

DO - 10.1016/j.disc.2008.04.007

M3 - Article

VL - 309

SP - 5596

EP - 5609

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 18

ER -

Broersma HJ, Fujisawa J, Marchal L, Paulusma D, Salman M, Yoshimoto K. λ-backbone colorings along pairwise disjoint stars and matchings. Discrete mathematics. 2009 Sep 28;309(18):5596-5609. https://doi.org/10.1016/j.disc.2008.04.007