H.J. Broersma
A new algorithm for on-line coloring bipartite graphs
Broersma, H.J.; Capponi, A.; Paulusma, D
Abstract
We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs on various subfamilies. The algorithm yields new upper bounds for the on-line chromatic number of bipartite graphs. We prove that the algorithm is on-line competitive for $P_7$-free bipartite graphs, i.e., that do not contain an induced path on seven vertices. The number of colors used by the on-line algorithm for $P_6$-free and $P_7$-free bipartite graphs is, respectively, bounded by roughly twice and roughly eight times the on-line chromatic number. In contrast, it is known that there exists no competitive on-line algorithm to color $P_6$-free (or $P_7$-free) bipartite graphs, i.e., for which the number of colors is bounded by any function depending only on the chromatic number.
Citation
Broersma, H., Capponi, A., & Paulusma, D. (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics, 22(1), 72-91. https://doi.org/10.1137/060668675
Journal Article Type | Article |
---|---|
Publication Date | Feb 1, 2008 |
Deposit Date | Oct 6, 2010 |
Publicly Available Date | Oct 7, 2010 |
Journal | SIAM Journal on Discrete Mathematics |
Print ISSN | 0895-4801 |
Electronic ISSN | 1095-7146 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 22 |
Issue | 1 |
Pages | 72-91 |
DOI | https://doi.org/10.1137/060668675 |
Public URL | https://durham-repository.worktribe.com/output/1548355 |
Files
Published Journal Article
(272 Kb)
PDF
Copyright Statement
© 2010 SIAM
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article