Reproduce “An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
The authors present a randomized polynomial-time algorithm for properly coloring graphs promised to be 3-colorable, without being given a valid coloring. It uses semidefinite-programming vector representations to find large independent sets, combined with a dense-graph method. For every fixed C>0, it uses O(n^0.1537) colors with probability at least 1−n^−C; this guarantee relies on genuine 3-colorability, not vector 3-colorability alone.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.