### Abstract

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

City | Rome |

Period | 29/05/06 → 31/05/06 |

### Fingerprint

### Keywords

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

### Cite this

*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

}

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

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.

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 -