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 Lovasz, Saks and Trotter. The algorithm is on-line competitive on various classes of H-free bipartite graphs, in particular P_6-free bipartite graphs and P_7-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 P_6-free (or P_7-free) bipartite graphs, i.e., for which the number of colors is bounded by any function only depending on the chromatic number.
展开▼
