On-line coloring of H-free bipartite graphs

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

doi:10.1007/11758471_28

On-line coloring of H-free bipartite graphs

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

9 Downloads (Pure)

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 language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings
Editors	Tiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	284-295
Number of pages	12
ISBN (Electronic)	978-3-540-34378-3
ISBN (Print)	978-3-540-34375-2
DOIs	https://doi.org/10.1007/11758471_28
Publication status	Published - 2006
Event	6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Italy Duration: 29 May 2006 → 31 May 2006 Conference number: 6

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3998
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Italian Conference on Algorithms and Complexity, CIAC 2006
Abbreviated title	CIAC
Country/Territory	Italy
City	Rome
Period	29/05/06 → 31/05/06

Keywords

EWI-8087
IR-63662
METIS-238710

Access to Document

10.1007/11758471_28

Cite this

@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",

address = "Germany",

note = "6th Italian Conference on Algorithms and Complexity, CIAC 2006, CIAC ; Conference date: 29-05-2006 Through 31-05-2006",

}

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 proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Broersma, H.J.

AU - Capponi, A.

AU - Paulusma, D.

N1 - Conference code: 6

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

T2 - 6th Italian Conference on Algorithms and Complexity, CIAC 2006

Y2 - 29 May 2006 through 31 May 2006

ER -

On-line coloring of H-free bipartite graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this