Skip to main content

Research Repository

Advanced Search

A new algorithm for on-line coloring bipartite graphs

Broersma, H.J.; Capponi, A.; Paulusma, D

A new algorithm for on-line coloring bipartite graphs Thumbnail


Authors

H.J. Broersma

A. Capponi



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







You might also like



Downloadable Citations