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 Lovász, 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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976)
Chrobak, M., Ślusarek, M.: Problem 84-23. Journal of Algorithms 5, 588 (1984)
Erlebach, T., Fiala, J.: On-line coloring of geometric intersection graphs. Computational Geometry: Theory and Applications 23, 243–255 (2002)
Gyárfás, A., Király, Z., Lehel, J.: On-line competitive coloring algorithms. Technical report TR-9703-1 (1997), Available at: http://www.cs.elte.hu/tr97/
Gyárfás, A., Király, Z., Lehel, J.: On-line 3-chromatic graphs. II. Critical graphs. Discrete Mathematics 177, 99–122 (1997)
Gyárfás, A., Lehel, J.: On-line and first-fit colorings of graphs. Journal of Graph Theory 12, 217–227 (1988)
Gyárfás, A., Lehel, J.: First fit and on-line chromatic number of families of graphs. Ars Combinatorica 29C, 168–176 (1990)
Gyárfás, A., Lehel, J.: Effective on-line coloring of P 5-free graphs. Combinatorica 11, 181–184 (1991)
Halldórsson, M.M.: Online coloring known graphs. Electronic Journal of Combinatorics 7, Research Paper 7, 9pp (2000)
Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM Journal on Discrete Mathematics 1, 526–530 (1988)
Kierstead, H.A.: Coloring graphs on-line. In: Fiat, Woeginger (eds.) Online Algorithms: the state of the art. LNCS, vol. 1442, pp. 281–305. Springer, Heidelberg (1998)
Kierstead, H., Penrice, S.G.: Radius two trees specify χ-bounded classes. Journal of Graph Theory 18, 119–129 (1994)
Kierstead, H., Penrice, S.G., Trotter, W.: On-line graph coloring and recursive graph theory. SIAM Journal on Discrete Mathematics 7, 72–89 (1994)
Kolossa, K.: On the on-line chromatic number of the family of on-line 3-chromatic graphs. Discrete Mathematics 150, 205–230 (1996)
Lovász, L., Saks, M., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics 75, 319–325 (1989)
Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs – a survey. Graphs and Combinatorics 20, 1–40 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Broersma, H.J., Capponi, A., Paulusma, D. (2006). On-Line Coloring of H-Free Bipartite Graphs. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_28
Download citation
DOI: https://doi.org/10.1007/11758471_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)