Improved upper bounds for λ-backbone colorings along matchings and stars

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

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

5 Citations (Scopus)

Abstract

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring for $G$ and $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$. The main outcome of earlier studies is that the minimum number $\ell$ of colors for which such colorings $V\to\{1,2,\ldots, \ell\}$ exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\lambda$) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on $\ell$ than the previously known bounds.
Original languageUndefined
Title of host publicationProceedings of SOFSEM 2007: Theory and Practice of Computer Science
EditorsJ. van Leeuwen, G.F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plásil
Place of PublicationBerlin
PublisherSpringer
Pages188-199
Number of pages12
ISBN (Print)978-3-540-69506-6
DOIs
Publication statusPublished - 13 Jul 2007

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
NumberLNCS4549
Volume4362
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • EWI-11097
  • IR-61929
  • METIS-241921

Cite this

Broersma, H. J., Marchal, L., Paulusma, D., & Salman, M. (2007). Improved upper bounds for λ-backbone colorings along matchings and stars. In J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, & F. Plásil (Eds.), Proceedings of SOFSEM 2007: Theory and Practice of Computer Science (pp. 188-199). [10.1007/978-3-540-69507-3] (Lecture Notes in Computer Science; Vol. 4362, No. LNCS4549). Berlin: Springer. https://doi.org/10.1007/978-3-540-69507-3_15, https://doi.org/10.1007/978-3-540-69507-3
Broersma, Haitze J. ; Marchal, L. ; Paulusma, Daniël ; Salman, M. / Improved upper bounds for λ-backbone colorings along matchings and stars. Proceedings of SOFSEM 2007: Theory and Practice of Computer Science. editor / J. van Leeuwen ; G.F. Italiano ; W. van der Hoek ; C. Meinel ; H. Sack ; F. Plásil. Berlin : Springer, 2007. pp. 188-199 (Lecture Notes in Computer Science; LNCS4549).
@inproceedings{ee2495ef4fd04e2f8541a35ceccc1df9,
title = "Improved upper bounds for λ-backbone colorings along matchings and stars",
abstract = "We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring for $G$ and $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$. The main outcome of earlier studies is that the minimum number $\ell$ of colors for which such colorings $V\to\{1,2,\ldots, \ell\}$ exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\lambda$) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on $\ell$ than the previously known bounds.",
keywords = "EWI-11097, IR-61929, METIS-241921",
author = "Broersma, {Haitze J.} and L. Marchal and Dani{\"e}l Paulusma and M. Salman",
note = "10.1007/978-3-540-69507-3",
year = "2007",
month = "7",
day = "13",
doi = "10.1007/978-3-540-69507-3_15",
language = "Undefined",
isbn = "978-3-540-69506-6",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "LNCS4549",
pages = "188--199",
editor = "{van Leeuwen}, J. and G.F. Italiano and {van der Hoek}, W. and C. Meinel and H. Sack and F. Pl{\'a}sil",
booktitle = "Proceedings of SOFSEM 2007: Theory and Practice of Computer Science",

}

Broersma, HJ, Marchal, L, Paulusma, D & Salman, M 2007, Improved upper bounds for λ-backbone colorings along matchings and stars. in J van Leeuwen, GF Italiano, W van der Hoek, C Meinel, H Sack & F Plásil (eds), Proceedings of SOFSEM 2007: Theory and Practice of Computer Science., 10.1007/978-3-540-69507-3, Lecture Notes in Computer Science, no. LNCS4549, vol. 4362, Springer, Berlin, pp. 188-199. https://doi.org/10.1007/978-3-540-69507-3_15, https://doi.org/10.1007/978-3-540-69507-3

Improved upper bounds for λ-backbone colorings along matchings and stars. / Broersma, Haitze J.; Marchal, L.; Paulusma, Daniël; Salman, M.

Proceedings of SOFSEM 2007: Theory and Practice of Computer Science. ed. / J. van Leeuwen; G.F. Italiano; W. van der Hoek; C. Meinel; H. Sack; F. Plásil. Berlin : Springer, 2007. p. 188-199 10.1007/978-3-540-69507-3 (Lecture Notes in Computer Science; Vol. 4362, No. LNCS4549).

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

TY - GEN

T1 - Improved upper bounds for λ-backbone colorings along matchings and stars

AU - Broersma, Haitze J.

AU - Marchal, L.

AU - Paulusma, Daniël

AU - Salman, M.

N1 - 10.1007/978-3-540-69507-3

PY - 2007/7/13

Y1 - 2007/7/13

N2 - We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring for $G$ and $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$. The main outcome of earlier studies is that the minimum number $\ell$ of colors for which such colorings $V\to\{1,2,\ldots, \ell\}$ exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\lambda$) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on $\ell$ than the previously known bounds.

AB - We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring for $G$ and $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$. The main outcome of earlier studies is that the minimum number $\ell$ of colors for which such colorings $V\to\{1,2,\ldots, \ell\}$ exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\lambda$) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on $\ell$ than the previously known bounds.

KW - EWI-11097

KW - IR-61929

KW - METIS-241921

U2 - 10.1007/978-3-540-69507-3_15

DO - 10.1007/978-3-540-69507-3_15

M3 - Conference contribution

SN - 978-3-540-69506-6

T3 - Lecture Notes in Computer Science

SP - 188

EP - 199

BT - Proceedings of SOFSEM 2007: Theory and Practice of Computer Science

A2 - van Leeuwen, J.

A2 - Italiano, G.F.

A2 - van der Hoek, W.

A2 - Meinel, C.

A2 - Sack, H.

A2 - Plásil, F.

PB - Springer

CY - Berlin

ER -

Broersma HJ, Marchal L, Paulusma D, Salman M. Improved upper bounds for λ-backbone colorings along matchings and stars. In van Leeuwen J, Italiano GF, van der Hoek W, Meinel C, Sack H, Plásil F, editors, Proceedings of SOFSEM 2007: Theory and Practice of Computer Science. Berlin: Springer. 2007. p. 188-199. 10.1007/978-3-540-69507-3. (Lecture Notes in Computer Science; LNCS4549). https://doi.org/10.1007/978-3-540-69507-3_15, https://doi.org/10.1007/978-3-540-69507-3