Exponential Time Approximation for Coloring 3-Colorable Graphs

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^ε)-color a 3-colorable graphs in time 2^Θ(n1-2ε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(Õ( nlog11/2r r³)) time, asymptotically improving upon the bound given by Atserias and Dalmau.