H.J. Broersma
Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
Broersma, H.J.; Marchal, L.; Paulusma, D.; Salman, A.N.M.
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 l-backbone coloring for G and 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 l. 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 l of colors, for which such colorings V® {1,2,Ľ,l} 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, l is at most a small additive constant (depending on l) 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 l than the previously known bounds.
Journal Article Type | Article |
---|---|
Publication Date | Mar 1, 2009 |
Deposit Date | Sep 9, 2009 |
Publicly Available Date | Mar 26, 2010 |
Journal | Discussiones mathematicae. Graph theory. |
Print ISSN | 1234-3099 |
Publisher | De Gruyter Open |
Peer Reviewed | Peer Reviewed |
Volume | 29 |
Issue | 1 |
Pages | 143-162 |
DOI | https://doi.org/10.7151/dmgt.1437 |
Keywords | Backbone coloring, Split graph, Matching, Star |
Public URL | https://durham-repository.worktribe.com/output/1527356 |
Publisher URL | http://www.discuss.wmie.uz.zgora.pl//gt/29_1/gt29-561.htm |
Files
Published Journal Article
(165 Kb)
PDF
You might also like
Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs
(2009)
Presentation / Conference Contribution
Three complexity results on coloring Pk-free graphs
(2009)
Presentation / Conference Contribution
The computational complexity of the parallel knock-out problem
(2006)
Presentation / Conference Contribution
On hamiltonicity of P3-dominated graphs
(2009)
Journal Article
Upper bounds and algorithms for parallel knock-out numbers
(2009)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search