2026-07-20T05:35:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4479 2024-03-06T10:35:06Z ddc:004 open_access

Coloring 3-colorable graphs with o(n^{1/5}) colors Kawarabayashi, Ken-ichi Thorup, Mikkel Approximation Algorithms Graph Coloring Recognizing 3-colorable graphs is one of the most famous NP-complete problems [Garey, Johnson, and Stockmeyer, STOC'74]. The problem of coloring 3-colorable graphs in polynomial time with as few colors as possible has been intensively studied: O(n^{1/2}) colors [Wigderson, STOC'82], O(n^{2/5}) colors [Blum, STOC'89], O(n^{3/8}) colors [Blum, FOCS'90], O(n^{1/4}) colors [Karger, Motwani and Sudan, FOCS'94], O(n^{3/14})=O(n^0.2142) colors [Blum and Karger, IPL'97], O(n^{0.2111}) colors [Arora, Chlamtac, and Charikar, STOC'06], and O(n^{0.2072}) colors [Chlamtac, FOCS'07]. Recently the authors got down to O(n^{0.2049}) colors [FOCS'12]. In this paper we get down to O(n^{0.19996})=o(n^{1/5}) colors. Since 1994, the best bounds have all been obtained balancing between combinatorial and semi-definite approaches. We present a new combinatorial recursion that only makes sense in collaboration with semi-definite programming. We specifically target the worst-case for semi-definite programming: high degrees. By focusing on the interplay, we obtained the biggest improvement in the exponent since 1997. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ken-ichi Kawarabayashi and Mikkel Thorup 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.458 urn:nbn:de:0030-drops-44797 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.458 eng https://creativecommons.org/licenses/by/3.0/legalcode