{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigxtpryu6oma4uivmu6xzwhzpgrybueqkaevk43vn7sj34jlg7bzi",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3me5xeduedzd2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.05904v1",
  "publishedAt": "2026-02-06T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Nikhil Bansal",
    "Neng Huang",
    "Euiwoong Lee"
  ],
  "textContent": "**Authors:** Nikhil Bansal, Neng Huang, Euiwoong Lee\n\nWe 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"
}