License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.458
URN: urn:nbn:de:0030-drops-44797
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4479/
Go to the corresponding LIPIcs Volume Portal

Kawarabayashi, Ken-ichi ; Thorup, Mikkel

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

pdf-format:
37.pdf (0.7 MB)

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], 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.

BibTeX - Entry

@InProceedings{kawarabayashi_et_al:LIPIcs:2014:4479,
  author =	{Ken-ichi Kawarabayashi and Mikkel Thorup},
  title =	{{Coloring 3-colorable graphs with o(n^{1/5}) colors}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{458--469},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4479},
  URN =		{urn:nbn:de:0030-drops-44797},
  doi =		{10.4230/LIPIcs.STACS.2014.458},
  annote =	{Keywords: Approximation Algorithms, Graph Coloring}
}

Keywords: Approximation Algorithms, Graph Coloring
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI