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.


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:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:© 2010 SIAM
Date accepted:No date available
Date deposited:07 October 2010
Date of first online publication:February 2008
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar