On-line coloring of H-free bipartite graphs

H.J. Broersma, A. Capponi, D. Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationAlgorithms and Complexity
Subtitle of host publication6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings
EditorsTiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages284-295
Number of pages12
ISBN (Electronic)978-3-540-34378-3
ISBN (Print)978-3-540-34375-2
DOIs
Publication statusPublished - 2006
Event6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Italy
Duration: 29 May 200631 May 2006
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3998
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th Italian Conference on Algorithms and Complexity, CIAC 2006
Abbreviated titleCIAC
CountryItaly
CityRome
Period29/05/0631/05/06

Keywords

  • EWI-8087
  • IR-63662
  • METIS-238710

Fingerprint Dive into the research topics of 'On-line coloring of H-free bipartite graphs'. Together they form a unique fingerprint.

  • Cite this

    Broersma, H. J., Capponi, A., & Paulusma, D. (2006). On-line coloring of H-free bipartite graphs. In T. Calamoneri, I. Finocchi, & G. F. Italiano (Eds.), Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings (pp. 284-295). (Lecture Notes in Computer Science; Vol. 3998). Berlin, Heidelberg: Springer. https://doi.org/10.1007/11758471_28