An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths
Piotr Micek, Veit Wiechert · Algorithmica · 2016
The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for $$P_9$$ -free bipartite graphs.