An on-line competitive algorithm for coloring bipartite graphs without long induced paths

DOI10.1007/S00453-016-0130-2zbMath1360.05065OpenAlexW1491462073WikidataQ59529322 ScholiaQ59529322MaRDI QIDQ524365

Piotr Micek, Veit Wiechert

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://depositonce.tu-berlin.de/handle/11303/6664

zbMATH Keywords

graph coloringon-line algorithmbipartite graphs

Mathematics Subject Classification ID

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

Related Items (2)

Online coloring of short intervals ⋮ 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
• An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs
• 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 bipartite graphs without long induced paths