### 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 language | Undefined |
---|---|

Pages (from-to) | 5596-5609 |

Number of pages | 14 |

Journal | Discrete mathematics |

Volume | 309 |

Issue number | 18 |

DOIs | |

Publication status | Published - 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