Coloring 3-Colorable Graphs with Low Threshold Rank

We present a new algorithm for finding large independent sets in 3-colorable graphs with small 1-sided threshold rank. Specifically, given an n-vertex 3-colorable graph whose uniform random walk matrix has at most r eigenvalues larger than ε, our algorithm finds a proper 3coloring on at least ( 1 2 -O(ε))n vertices in time n O(r/ε 2 ) . This extends and improves upon the result of Bafna, Hsieh, and Kothari [BHK25] on 1-sided expanders. Furthermore, an independent work by Buhai, Hua, Steurer, and Vári-Kakas [BHSV25] shows that it is UG-hard to properly 3-color more than ( 1 2 + ε)n vertices, thus establishing the tightness of our result. Our proof is short and simple, relying on the observation that for any distribution over proper 3-colorings, the correlation across an edge must be large if the marginals of the endpoints are not concentrated on any single color. Notably, this property fails for 4-colorings, which is consistent with the hardness result of [BHK25] for 4-colorable 1-sided expanders.