Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

A new algorithm for on-line coloring bipartite graphs.

Broersma, H.J. and Capponi, A. and Paulusma, Daniel (2008) 'A new algorithm for on-line coloring bipartite graphs.', SIAM journal on discrete mathematics., 22 (1). pp. 72-91.

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.

Item Type:Article
Full text:PDF - Published Version (266Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1137/060668675
Publisher statement:© 2010 SIAM
Record Created:07 Oct 2010 12:20
Last Modified:03 Apr 2013 13:22

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library