We present a polynomial-time randomized algorithm that colors every n-vertex $3$-colorable graph with O(n0.1537) colors. This improves upon the previous bound of O(n0.1954) colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an n1/6 + o(1)-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve O(n0.1537) colors.
No takes yet. Share an insight, caveat, or question.
Deguchi et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: