Approximation Algorithms for Partially Colorable Graphs

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 $α\leq 1$ and $k \in \mathbb{Z}^+$, we say that a graph $G=(V,E)$ is $α$-partially $k$-colorable, if there exists a subset $S\subset V$ of cardinality $ |S | \geq α| V |$ such that the graph induced on $S$ is $k$-colorable. Partial $k$-colorability is a more robust structural property of a graph than $k$-colorability. For graphs that arise in practice, partial $k$-colorability might be a better notion to use than $k$-colorability, since data arising in practice often contains various forms of noise. We give a polynomial time algorithm that takes as input a $(1 - ε)$-partially $3$-colorable graph $G$ and a constant $γ\in [ε, 1/10]$, and colors a $(1 - ε/γ)$ fraction of the vertices using $\tilde{O}\left(n^{0.25 + O(γ^{1/2})} \right)$ colors. We also study natural semi-random families of instances of partially $3$-colorable graphs and partially $2$-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances.