## Abstract

Given an integer λ ≥ 2, a graph G = (V, E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring of (G, H) is a proper vertex coloring V → {1, 2, ...} of G, in which the colors assigned to adjacent vertices in H differ by at least λ. 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 ℓ for which a λ-backbone coloring of (G, S) with colors in {1, ..., ℓ} exists can roughly differ by a multiplicative factor of at most 2 - frac(1, λ) from the chromatic number χ (G). For the special case of matching backbones this factor is roughly 2 - frac(2, λ + 1). We also show that the computational complexity of the problem "Given a graph G with a star backbone S, and an integer ℓ, is there a λ-backbone coloring of (G, S) with colors in {1, ..., ℓ}?" jumps from polynomially solvable to NP-complete between ℓ = λ + 1 and ℓ = λ + 2 (the case ℓ = λ + 2 is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.

Original language | English |
---|---|

Pages (from-to) | 5596-5609 |

Number of pages | 14 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 18 |

DOIs | |

Publication status | Published - 2009 Sept 28 |

Externally published | Yes |

## Keywords

- Matching
- Star
- λ-backbone coloring
- λ-backbone coloring number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics