A new algorithm for on-line coloring bipartite graphs

Haitze J. Broersma, A. Capponi, Daniël Paulusma

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)

Abstract

We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs on various subfamilies. The algorithm yields new upper bounds for the on-line chromatic number of bipartite graphs. We prove that the algorithm is on-line competitive for $P_7$-free bipartite graphs, i.e., that do not contain an induced path on seven vertices. The number of colors used by the on-line algorithm for $P_6$-free and $P_7$-free bipartite graphs is, respectively, bounded by roughly twice and 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 depending only on the chromatic number.
Original languageUndefined
Article number10.1137/060668675
Pages (from-to)72-91
Number of pages20
JournalSIAM journal on discrete mathematics
Volume22
Issue numberWoTUG-31/1
DOIs
Publication statusPublished - Feb 2008

Keywords

  • IR-62553
  • EWI-14147
  • METIS-254918

Cite this

Broersma, Haitze J. ; Capponi, A. ; Paulusma, Daniël. / A new algorithm for on-line coloring bipartite graphs. In: SIAM journal on discrete mathematics. 2008 ; Vol. 22, No. WoTUG-31/1. pp. 72-91.
@article{e0f152c0733c4d569a2f9144d2805125,
title = "A new algorithm for on-line coloring bipartite graphs",
abstract = "We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs on various subfamilies. The algorithm yields new upper bounds for the on-line chromatic number of bipartite graphs. We prove that the algorithm is on-line competitive for $P_7$-free bipartite graphs, i.e., that do not contain an induced path on seven vertices. The number of colors used by the on-line algorithm for $P_6$-free and $P_7$-free bipartite graphs is, respectively, bounded by roughly twice and 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 depending only on the chromatic number.",
keywords = "IR-62553, EWI-14147, METIS-254918",
author = "Broersma, {Haitze J.} and A. Capponi and Dani{\"e}l Paulusma",
note = "10.1137/060668675",
year = "2008",
month = "2",
doi = "10.1137/060668675",
language = "Undefined",
volume = "22",
pages = "72--91",
journal = "SIAM journal on discrete mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "WoTUG-31/1",

}

Broersma, HJ, Capponi, A & Paulusma, D 2008, 'A new algorithm for on-line coloring bipartite graphs' SIAM journal on discrete mathematics, vol. 22, no. WoTUG-31/1, 10.1137/060668675, pp. 72-91. https://doi.org/10.1137/060668675

A new algorithm for on-line coloring bipartite graphs. / Broersma, Haitze J.; Capponi, A.; Paulusma, Daniël.

In: SIAM journal on discrete mathematics, Vol. 22, No. WoTUG-31/1, 10.1137/060668675, 02.2008, p. 72-91.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A new algorithm for on-line coloring bipartite graphs

AU - Broersma, Haitze J.

AU - Capponi, A.

AU - Paulusma, Daniël

N1 - 10.1137/060668675

PY - 2008/2

Y1 - 2008/2

N2 - We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs on various subfamilies. The algorithm yields new upper bounds for the on-line chromatic number of bipartite graphs. We prove that the algorithm is on-line competitive for $P_7$-free bipartite graphs, i.e., that do not contain an induced path on seven vertices. The number of colors used by the on-line algorithm for $P_6$-free and $P_7$-free bipartite graphs is, respectively, bounded by roughly twice and 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 depending only on the chromatic number.

AB - We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs on various subfamilies. The algorithm yields new upper bounds for the on-line chromatic number of bipartite graphs. We prove that the algorithm is on-line competitive for $P_7$-free bipartite graphs, i.e., that do not contain an induced path on seven vertices. The number of colors used by the on-line algorithm for $P_6$-free and $P_7$-free bipartite graphs is, respectively, bounded by roughly twice and 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 depending only on the chromatic number.

KW - IR-62553

KW - EWI-14147

KW - METIS-254918

U2 - 10.1137/060668675

DO - 10.1137/060668675

M3 - Article

VL - 22

SP - 72

EP - 91

JO - SIAM journal on discrete mathematics

JF - SIAM journal on discrete mathematics

SN - 0895-4801

IS - WoTUG-31/1

M1 - 10.1137/060668675

ER -