{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T09:53:10Z","timestamp":1790675590897,"version":"4.1.0"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>We give a new proof showing that it is NP-hard to color a 3-colorable graph using just 4 colors. This result is already known , [S. Khanna, N. Linial, and S. Safra, Combinatorica, 20 (2000), pp. 393--415], but our proof is novel because it does not rely on the PCP theorem, while the known one does. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor $n^{\\epsilon}$ hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem [M. Bellare, O. Goldreich, and M. Sudan, SIAM J. Comput., 27 (1998), pp. 805--915].<\/jats:p>\n                  <jats:p>Another aspect in which our proof is novel is in its use of the PCP theorem to show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs (this hardness result does not seem to follow from the earlier reduction of Khanna, Linial, and Safra). We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires $n^{\\Omega(1)}$ colors. Our proof technique also shows that there is an $\\varepsilon_0 &gt; 0$ such that it is NP-hard to legally 4-color even a $(1-\\varepsilon_0)$ fraction of the edges of a 3-colorable graph.<\/jats:p>","DOI":"10.1137\/s0895480100376794","type":"journal-article","created":{"date-parts":[[2004,7,6]],"date-time":"2004-07-06T21:04:35Z","timestamp":1089147875000},"page":"30-40","source":"Crossref","is-referenced-by-count":41,"title":["On the Hardness of 4-Coloring a 3-Colorable Graph"],"prefix":"10.1137","volume":"18","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"R4","unstructured":"A. Blum,\n                      Algorithms for Approximate Graph Coloring\n                      , Ph.D. thesis, Laboratory for Computer Science, MIT, Cambridge, MA, 1991."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176586"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer,\n                      Improved hardness results for approximating the chromatic number\n                      , in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 1995, pp. 414\u2013421.","DOI":"10.1109\/SFCS.1995.492572"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377165"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90246-6"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R18","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, and S. Khanna,\n                      Approximating Longest Directed Path\n                      , Report TR03\u2010032, Electronic Colloquium on Computational Complexity (ECCC), http:\/\/eccc.uni\u2010trier.de\/eccc\u2010reports\/2003\/TR03\u2010032\/index.html (2003)."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202286"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480100376794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:20:11Z","timestamp":1787322011000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480100376794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0895480100376794"],"URL":"https:\/\/doi.org\/10.1137\/s0895480100376794","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}