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

Broersma, H.J.
and
Marchal, L.
and
Paulusma, D.
and
Salman, A.N.M.
(2007)
*Improved upper bounds for -backbone colorings along matchings and stars.*
In: Proceedings of SOFSEM 2007: Theory and Practice of Computer Science, 20-26 Jan 2007, Harrachov, Czech Republic (pp. pp. 188-199).

PDF
Restricted to UT campus only : Request a copy 414kB |

Abstract: | We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph and a spanning subgraph of (the backbone of ), a -backbone coloring for and is a proper vertex coloring of in which the colors assigned to adjacent vertices in differ by at least . The main outcome of earlier studies is that the minimum number of colors for which such colorings 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, is at most a small additive constant (depending on ) 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 than the previously known bounds. |

Item Type: | Conference or Workshop Item |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/61929 |

Official URL: | http://dx.doi.org/10.1007/978-3-540-69507-3_15 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 241921