Group for Research in Decision Analysis

# Online algorithms for the maximum k-colorable subgraph problem

## Alain Hertz, Romain Montagné, and François Gagnon

The maximum $$k$$-colorable subgraph problem ($$k$$-MCSP) is to color as many vertices as possible with at most $$k$$ colors, such that no two adjacent vertices share the same color. We consider online algorithms for this $$\mathcal{NP}$$-hard problem, and give bounds on their competitive ratio. We then consider a large family $$\cal{A}$$ of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in $$\cal{A}$$ can produce an optimal solution to the $$k$$-MCSP. We then compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. We finally consider the case where vertices colored at an early stage can receive a new color later on, as long as they remain colored.

, 23 pages