Exponential Time Approximation for Coloring 3-Colorable Graphs

Abstract

The problem of efficiently coloring $3$-colorable graphs with few colors has received much attention on both the algorithmic and inapproximability fronts. We consider exponential time approximations, in which given a parameter $r$, we aim to develop an $r$-approximation algorithm with the best possible runtime, providing a tradeoff between runtime and approximation ratio. In this vein, an algorithm to $O(n^{\epsilon })$-color a 3-colorable graphs in time $2^{\hat{I}˜(n^{1-2\epsilon }\log (n))}$ is given in (Atserias and Dalmau, SODA 2022.) We build on tools developed in (Bansal et al., Algorithmic, 2019) to obtain an algorithm to color $3$-colorable graphs with $O(r)$ colors in $\exp \left(\tilde{O}\left(\frac{n{\log }^{11/2}r}{r^3}\right)\right)$ time, asymptotically improving upon the bound given by Atserias and Dalmau.