An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs

DOI10.1007/978-3-319-13075-0_41zbMath1359.05126arXiv1502.00859OpenAlexW2280668383MaRDI QIDQ2942656

Piotr Micek, Veit Wiechert

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.00859

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (2)

An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ Open Problems on Graph Coloring for Special Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line 3-chromatic graphs. II: Critical graphs
• Lower Bounds for On-line Graph Colorings
• The relative worst order ratio for online algorithms
• On-Line Coloring of H-Free Bipartite Graphs
• A New Algorithm for On-line Coloring Bipartite Graphs
• On-line and first fit colorings of graphs
• On-Line Coloring and Recursive Graph Theory
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $

This page was built for publication: An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs