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