### Abstract

Original language | Undefined |
---|---|

Title of host publication | Proceedings of SOFSEM 2007: Theory and Practice of Computer Science |

Editors | J. van Leeuwen, G.F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plásil |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 188-199 |

Number of pages | 12 |

ISBN (Print) | 978-3-540-69506-6 |

DOIs | |

Publication status | Published - 13 Jul 2007 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Number | LNCS4549 |

Volume | 4362 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

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

### Cite this

*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

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -