On-line coloring of H-free bipartite graphs.

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

Abstract

We present a new on-line algorithm for coloring bipartite graphs. This yields a new upper bound on the on-line chromatic number of bipartite graphs, improving a bound due to Lovász, Saks and Trotter. The algorithm is on-line competitive on various classes of H - free bipartite graphs, in particular P6-free bipartite graphs and P7-free bipartite graphs, i.e., that do not contain an induced path on six, respectively seven vertices. The number of colors used by the on-line algorithm in these particular cases is bounded by roughly twice, respectively roughly eight times the on-line chromatic number. In contrast, it is known that there exists no competitive on-line algorithm to color P6-free (or P7-free) bipartite graphs, i.e., for which the number of colors is bounded by any function only depending on the chromatic number.

Citation

Broersma, H. J., Capponi, A., & Paulusma, D. (2006, May). On-line coloring of H-free bipartite graphs. Presented at 6th Italian Conference on Algorithms and Complexity (CIAC 2006)., Rome, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 6th Italian Conference on Algorithms and Complexity (CIAC 2006).
• Start Date: May 29, 2006
• End Date: May 31, 2006
• Publication Date: 2006
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 3998
• Pages: 284-295
• Series Title: Lecture Notes in Computer Science.
• DOI: https://doi.org/10.1007/11758471_28
• Keywords: on-line coloring, bipartite graph, H-free graph
• Public URL: https://durham-repository.worktribe.com/output/1161971