An on-line competitive algorithm for coloring bipartite graphs without long induced paths
classification
💻 cs.DS
math.CO
keywords
graphsbipartitealgorithmcoloringcompetitiveon-lineinducedcertain
read the original abstract
The existence of an on-line competitive algorithm for coloring bipartite graphs remains 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 a new on-line competitive coloring algorithm for $P_9$-free bipartite graphs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.