{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T05:06:09Z","timestamp":1777957569166,"version":"3.51.4"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,2,28]],"date-time":"2017-02-28T00:00:00Z","timestamp":1488240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Advanced Grant from the Danish Council for Independent Research under the Sapere Aude research carrier programme"},{"DOI":"10.13039\/501100009024","name":"JST ERATO Kawarabayashi Large Graph Project","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"name":"AT8T Labs--Research"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,2,28]]},"abstract":"<jats:p>\n            We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We first present a new combinatorial algorithm using\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/11<\/jats:sup>\n            ) colors. This is the first combinatorial improvement since Blum\u2019s\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/8<\/jats:sup>\n            ) bound from FOCS\u201990. Like Blum\u2019s algorithm, our new algorithm composes immediately with recent semi-definite programming approaches, and improves the best bound for the polynomial time algorithm for the coloring of 3-colorable graphs from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.2072<\/jats:sup>\n            ) colors by Chlamtac from FOCS\u201907 to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.2049<\/jats:sup>\n            ) colors.\n          <\/jats:p>\n          <jats:p>\n            Next, we develop a new recursion tailored for combination with semi-definite approaches, bringing us further down to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.19996<\/jats:sup>\n            ) colors.\n          <\/jats:p>","DOI":"10.1145\/3001582","type":"journal-article","created":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T14:54:11Z","timestamp":1490367251000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Coloring 3-Colorable Graphs with Less than\n            <i>n<\/i>\n            <sup>1\/5<\/sup>\n            Colors"],"prefix":"10.1145","volume":"64","author":[{"given":"Ken-Ichi","family":"Kawarabayashi","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2017,3,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132548"},{"key":"e_1_2_1_2_1","volume-title":"Proc. APPROX-RANDOM. 1--12","author":"Arora S.","unstructured":"S. Arora and R. Ge . 2011. New tools for graph coloring . In Proc. APPROX-RANDOM. 1--12 . S. Arora and R. Ge. 2011. New tools for graph coloring. In Proc. APPROX-RANDOM. 1--12."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840398"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176586"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.13"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431391"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.16"},{"key":"e_1_2_1_18_1","first-page":"458","article-title":"Coloring 3-colorable graphs with o(n1\/5) colors. In Proc. 31st STACS","volume":"25","author":"Kawarabayashi Ken-Ichi","year":"2014","unstructured":"Ken-Ichi Kawarabayashi and Mikkel Thorup . 2014 . Coloring 3-colorable graphs with o(n1\/5) colors. In Proc. 31st STACS , LIPIcs 25. 458 -- 469 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2014\/4479 Ken-Ichi Kawarabayashi and Mikkel Thorup. 2014. Coloring 3-colorable graphs with o(n1\/5) colors. In Proc. 31st STACS, LIPIcs 25. 458--469. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2014\/4479","journal-title":"LIPIcs"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365707"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3001582","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3001582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:38:42Z","timestamp":1750221522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3001582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,28]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2,28]]}},"alternative-id":["10.1145\/3001582"],"URL":"https:\/\/doi.org\/10.1145\/3001582","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,28]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}