# Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

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

9 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 $\gamma$-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 $\gamma$. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. 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 path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\gamma$) higher than the chromatic number. 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 language Undefined 143-162 20 Discussiones mathematicae. Graph theory 29 1 https://doi.org/10.7151/dmgt.1437 Published - Mar 2009

• EWI-15830
• METIS-263962
• IR-67842

### Cite this

@article{115337c33fbf45f2811036f9eb6de44b,
title = "Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number",
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 $\gamma$-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 $\gamma$. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. 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 path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\gamma$) higher than the chromatic number. 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-15830, METIS-263962, IR-67842",
author = "Broersma, {Haitze J.} and Bert Marchal and Dani{\"e}l Paulusma and M. Salman",
year = "2009",
month = "3",
doi = "10.7151/dmgt.1437",
language = "Undefined",
volume = "29",
pages = "143--162",
journal = "Discussiones mathematicae. Graph theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",
number = "1",

}

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. / Broersma, Haitze J.; Marchal, Bert; Paulusma, Daniël; Salman, M.

In: Discussiones mathematicae. Graph theory, Vol. 29, No. 1, 03.2009, p. 143-162.

TY - JOUR

T1 - Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

AU - Broersma, Haitze J.

AU - Marchal, Bert

AU - Paulusma, Daniël

AU - Salman, M.

PY - 2009/3

Y1 - 2009/3

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 $\gamma$-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 $\gamma$. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. 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 path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\gamma$) higher than the chromatic number. 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 $\gamma$-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 $\gamma$. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. 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 path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\gamma$) higher than the chromatic number. 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-15830

KW - METIS-263962

KW - IR-67842

U2 - 10.7151/dmgt.1437

DO - 10.7151/dmgt.1437

M3 - Article

VL - 29

SP - 143

EP - 162

JO - Discussiones mathematicae. Graph theory

JF - Discussiones mathematicae. Graph theory

SN - 1234-3099

IS - 1

ER -