# On-line coloring of H-free bipartite graphs

Broersma, H.J.
and
Capponi, A.
and
Paulusma, D.
(2006)
*On-line coloring of H-free bipartite graphs.*
In: Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC 2006), 29-31 May 2006, Rome, Italy (pp. pp. 284-295).

PDF
Restricted to UT campus only : Request a copy 500kB |

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

Item Type: | Conference or Workshop Item |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/63662 |

Official URL: | http://dx.doi.org/10.1007/11758471_28 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 238710