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^ (n^{1-2 (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 (O (n^{11/2r} r³) ) time, asymptotically improving upon the bound given by Atserias and Dalmau.