An On line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths
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$$P9 free bipartite graphs.
Algorithmica