Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910013088333824 |
|---|---|
| author | Bansal, Nikhil Huang, Neng Lee, Euiwoong |
| author_facet | Bansal, Nikhil Huang, Neng Lee, Euiwoong |
| contents | 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.19747})$ by Kawarabayashi, Thorup, and Yoneda [STOC 2024]. Our result constitutes the first progress in nearly two decades on SDP-based approaches to this problem.
The earlier SDP-based algorithms of Arora, Chlamtáč, and Charikar [STOC 2006] and Chlamtáč [FOCS 2007] rely on extracting a large independent set from a suitably "random-looking" second-level neighborhood, under the assumption that the KMS algorithm [Karger, Motwani, and Sudan, JACM 1998] fails to find one globally. We extend their analysis to third-level neighborhoods. We then come up with a new vector $5/2$-coloring, which allows us to extract a large independent set from some third-level neighborhood. The new vector coloring construction may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05904 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs Bansal, Nikhil Huang, Neng Lee, Euiwoong Data Structures and Algorithms 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.19747})$ by Kawarabayashi, Thorup, and Yoneda [STOC 2024]. Our result constitutes the first progress in nearly two decades on SDP-based approaches to this problem. The earlier SDP-based algorithms of Arora, Chlamtáč, and Charikar [STOC 2006] and Chlamtáč [FOCS 2007] rely on extracting a large independent set from a suitably "random-looking" second-level neighborhood, under the assumption that the KMS algorithm [Karger, Motwani, and Sudan, JACM 1998] fails to find one globally. We extend their analysis to third-level neighborhoods. We then come up with a new vector $5/2$-coloring, which allows us to extract a large independent set from some third-level neighborhood. The new vector coloring construction may be of independent interest. |
| title | Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.05904 |