Exponential Time Approximation for Coloring 3-Colorable Graphs
<|reference_start|>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^\varepsilon)$-color a 3-colorable graphs in time $2^{\Theta(n^{1-2\varepsilon}\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.<|reference_end|>
@article{guruswami2024exponential,
    title={Exponential Time Approximation for Coloring 3-Colorable Graphs},
    author={Venkatesan Guruswami and Rhea Jain},
    journal={arXiv preprint arXiv:2406.15563},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.15563},
    primaryClass={cs.DS cs.DM}
}