Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs

Nikhil Bansal, Neng Huang, Euiwoong Lee

We present a polynomial-time algorithm that colors any 3-colorable $n$-vertex graph using $O(n^{0.19539})$ colors, improving upon the previous best bound of $\widetilde{O}(n^{0.197…