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.

PDF
Restricted to UT campus only: Request a copy
488Kb

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 $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.
Item Type:	Conference or Workshop Item
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 238710