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 Citationer (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.

Originalsprog	Engelsk
Titel	31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Redaktører	Ernst W. Mayr, Natacha Portier
Antal sider	12
Forlag	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato	1 mar. 2014
Sider	458-469
ISBN (Trykt)	978-3-939897-65-1
DOI	https://doi.org/10.4230/LIPIcs.STACS.2014.458
Status	Udgivet - 1 mar. 2014
Begivenhed	31st Symposium on Theoretical Aspects of Computer Science - ENS Lyon, Lyon, Frankrig Varighed: 5 mar. 2014 → 8 mar. 2014 Konferencens nummer: 31

Konference

Konference	31st Symposium on Theoretical Aspects of Computer Science
Nummer	31
Lokation	ENS Lyon
Land/Område	Frankrig
By	Lyon
Periode	05/03/2014 → 08/03/2014

Navn	Leibniz International Proceedings in Informatics
Vol/bind	25
ISSN	1868-8969

Adgang til dokumentet

10.4230/LIPIcs.STACS.2014.458Licens: CC BY

Coloring 3-colorable graphs with o(n 1/5) colorsForlagets udgivne version, 709 KBLicens: CC BY

Citationsformater

Kawarabayashi, K., & Thorup, M. (2014). Coloring 3-colorable graphs with o(n ^1/5) colors. I E. W. Mayr, & N. Portier (red.), 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) (s. 458-469). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics Bind 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). red. / Ernst W. Mayr; Natacha Portier. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. s. 458-469 (Leibniz International Proceedings in Informatics, Bind 25).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Kawarabayashi, K & Thorup, M 2014, Coloring 3-colorable graphs with o(n ^1/5) colors. i EW Mayr & N Portier (red), 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, bind 25, s. 458-469, 31st Symposium on Theoretical Aspects of Computer Science, Lyon, Frankrig, 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 -