Approximation Algorithms for Partially Colorable Graphs

Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury

Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For $\alpha \le 1$ and $k \in \m…