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

Fingerprint

Bipartite Graph
Colouring
Chromatic number
Upper bound
Path
Color

Keywords

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

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
Broersma, H.J. ; Capponi, A. ; Paulusma, D. / On-line coloring of H-free bipartite graphs. Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. editor / Tiziana Calamoneri ; Irene Finocchi ; Giuseppe F. Italiano. Berlin, Heidelberg : Springer, 2006. pp. 284-295 (Lecture Notes in Computer Science).
@inproceedings{9565843e402c456e885b76870a70ee41,
title = "On-line coloring of H-free bipartite graphs",
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.",
keywords = "EWI-8087, IR-63662, METIS-238710",
author = "H.J. Broersma and A. Capponi and D. Paulusma",
year = "2006",
doi = "10.1007/11758471_28",
language = "English",
isbn = "978-3-540-34375-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "284--295",
editor = "Tiziana Calamoneri and Irene Finocchi and Italiano, {Giuseppe F.}",
booktitle = "Algorithms and Complexity",

}

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

On-line coloring of H-free bipartite graphs. / Broersma, H.J.; Capponi, A.; Paulusma, D.

Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. ed. / Tiziana Calamoneri; Irene Finocchi; Giuseppe F. Italiano. Berlin, Heidelberg : Springer, 2006. p. 284-295 (Lecture Notes in Computer Science; Vol. 3998).

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

TY - GEN

T1 - On-line coloring of H-free bipartite graphs

AU - Broersma, H.J.

AU - Capponi, A.

AU - Paulusma, D.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - EWI-8087

KW - IR-63662

KW - METIS-238710

U2 - 10.1007/11758471_28

DO - 10.1007/11758471_28

M3 - Conference contribution

SN - 978-3-540-34375-2

T3 - Lecture Notes in Computer Science

SP - 284

EP - 295

BT - Algorithms and Complexity

A2 - Calamoneri, Tiziana

A2 - Finocchi, Irene

A2 - Italiano, Giuseppe F.

PB - Springer

CY - Berlin, Heidelberg

ER -

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