Coloring 3-colorable graphs with o(n 1/5) colors

Ken-ichi Kawarabayashi; Mikkel Thorup

doi:10.4230/LIPIcs.STACS.2014.458

Coloring 3-colorable graphs with o(n ^1/5) colors

Ken-ichi Kawarabayashi, Mikkel Thorup

10 Citations (Scopus)

2344 Downloads (Pure)

Abstract

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], Õ(n^2/5) colors [Blum STOC'89], Õ (n^3/8) colors [Blum FOCS'90], O(n^1/4) colors [Karger, Motwani, Sudan FOCS'94], Õ (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.

Original language	English
Title of host publication	31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Editors	Ernst W. Mayr, Natacha Portier
Number of pages	12
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	1 Mar 2014
Pages	458-469
ISBN (Print)	978-3-939897-65-1
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2014.458
Publication status	Published - 1 Mar 2014
Event	31st Symposium on Theoretical Aspects of Computer Science - ENS Lyon, Lyon, France Duration: 5 Mar 2014 → 8 Mar 2014 Conference number: 31

Conference

Conference	31st Symposium on Theoretical Aspects of Computer Science
Number	31
Location	ENS Lyon
Country/Territory	France
City	Lyon
Period	05/03/2014 → 08/03/2014

Series	Leibniz International Proceedings in Informatics
Volume	25
ISSN	1868-8969

Access to Document

10.4230/LIPIcs.STACS.2014.458Licence: CC BY

Coloring 3-colorable graphs with o(n 1/5) colorsFinal published version, 709 KBLicence: CC BY

Cite this

Kawarabayashi, K., & Thorup, M. (2014). Coloring 3-colorable graphs with o(n ^1/5) colors. In E. W. Mayr, & N. Portier (Eds.), 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) (pp. 458-469). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics Vol. 25 https://doi.org/10.4230/LIPIcs.STACS.2014.458

Coloring 3-colorable graphs with o(n ^1/5) colors. / Kawarabayashi, Ken-ichi; Thorup, Mikkel.

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). ed. / Ernst W. Mayr; Natacha Portier. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. p. 458-469 (Leibniz International Proceedings in Informatics, Vol. 25).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Kawarabayashi, K & Thorup, M 2014, Coloring 3-colorable graphs with o(n ^1/5) colors. in EW Mayr & N Portier (eds), 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, vol. 25, pp. 458-469, 31st Symposium on Theoretical Aspects of Computer Science, Lyon, France, 05/03/2014. https://doi.org/10.4230/LIPIcs.STACS.2014.458

@inproceedings{abedd9ca5cc3484d821b6e55533a98dc,

title = "Coloring 3-colorable graphs with o(n 1/5) colors",

abstract = "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(n1/2) colors [Wigderson STOC'82], {\~O}(n2/5) colors [Blum STOC'89], {\~O} (n3/8) colors [Blum FOCS'90], O(n1/4) colors [Karger, Motwani, Sudan FOCS'94], {\~O} (n3/14) = O(n0.2142) colors [Blum and Karger IPL'97], O(n0.2111) colors [Arora, Chlamtac, and Charikar STOC'06], and O(n0.2072) colors [Chlamtac FOCS'07]. Recently the authors got down to O(n0.2049) colors [FOCS'12]. In this paper we get down to O(n0.19996) = o(n1/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.",

author = "Ken-ichi Kawarabayashi and Mikkel Thorup",

note = "Creative Commons License; 31st Symposium on Theoretical Aspects of Computer Science, STACS 2014 ; Conference date: 05-03-2014 Through 08-03-2014",

year = "2014",

month = mar,

day = "1",

doi = "10.4230/LIPIcs.STACS.2014.458",

language = "English",

isbn = "978-3-939897-65-1",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "458--469",

editor = "Mayr, {Ernst W.} and Natacha Portier",

booktitle = "31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)",

}

TY - GEN

T1 - Coloring 3-colorable graphs with o(n 1/5) colors

AU - Kawarabayashi, Ken-ichi

AU - Thorup, Mikkel

N1 - Conference code: 31

PY - 2014/3/1

Y1 - 2014/3/1

N2 - 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(n1/2) colors [Wigderson STOC'82], Õ(n2/5) colors [Blum STOC'89], Õ (n3/8) colors [Blum FOCS'90], O(n1/4) colors [Karger, Motwani, Sudan FOCS'94], Õ (n3/14) = O(n0.2142) colors [Blum and Karger IPL'97], O(n0.2111) colors [Arora, Chlamtac, and Charikar STOC'06], and O(n0.2072) colors [Chlamtac FOCS'07]. Recently the authors got down to O(n0.2049) colors [FOCS'12]. In this paper we get down to O(n0.19996) = o(n1/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.

AB - 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(n1/2) colors [Wigderson STOC'82], Õ(n2/5) colors [Blum STOC'89], Õ (n3/8) colors [Blum FOCS'90], O(n1/4) colors [Karger, Motwani, Sudan FOCS'94], Õ (n3/14) = O(n0.2142) colors [Blum and Karger IPL'97], O(n0.2111) colors [Arora, Chlamtac, and Charikar STOC'06], and O(n0.2072) colors [Chlamtac FOCS'07]. Recently the authors got down to O(n0.2049) colors [FOCS'12]. In this paper we get down to O(n0.19996) = o(n1/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.

U2 - 10.4230/LIPIcs.STACS.2014.458

DO - 10.4230/LIPIcs.STACS.2014.458

M3 - Article in proceedings

SN - 978-3-939897-65-1

T3 - Leibniz International Proceedings in Informatics

SP - 458

EP - 469

BT - 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

A2 - Mayr, Ernst W.

A2 - Portier, Natacha

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 31st Symposium on Theoretical Aspects of Computer Science

Y2 - 5 March 2014 through 8 March 2014

ER -