{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:44Z","timestamp":1772313224134,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403279","type":"print"},{"value":"9783642403286","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_17","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"233-243","source":"Crossref","is-referenced-by-count":15,"title":["Improved Hardness of Approximating Chromatic Number"],"prefix":"10.1007","author":[{"given":"Sangxia","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In: FOCS, pp. 600\u2013609 (2001)","DOI":"10.1109\/SFCS.2001.959936"},{"key":"17_CR2","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Wigderson, A.: A new approximate graph coloring algorithm. In: STOC, pp. 325\u2013329 (1982)","DOI":"10.1145\/800070.802207"},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01840398","volume":"5","author":"B. Berger","year":"1990","unstructured":"Berger, B., Rompel, J.: A better performance guarantee for approximate graph coloring. Algorithmica\u00a05(3), 459\u2013466 (1990)","journal-title":"Algorithmica"},{"issue":"2","key":"17_CR5","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D.R. Karger","year":"1998","unstructured":"Karger, D.R., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM\u00a045(2), 246\u2013265 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"17_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A. Blum","year":"1997","unstructured":"Blum, A., Karger, D.R.: An \n                    \n                      \n                    \n                    ${\\tilde{O}}(n^{3\/14})$\n                  -coloring algorithm for 3-colorable graphs. Inf. Process. Lett.\u00a061(1), 49\u201353 (1997)","journal-title":"Inf. Process. Lett."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: Combinatorial coloring of 3-colorable graphs. In: FOCS, pp. 68\u201375 (2012)","DOI":"10.1109\/FOCS.2012.16"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/1132516.1132548","volume-title":"Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC 2006","author":"S. Arora","year":"2006","unstructured":"Arora, S., Chlamtac, E.: New approximation guarantee for chromatic number. In: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 215\u2013224. ACM, New York (2006)"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: FOCS, pp. 691\u2013701 (2007)","DOI":"10.1109\/FOCS.2007.4389537"},{"issue":"3","key":"17_CR10","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s004930070013","volume":"20","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica\u00a020(3), 393\u2013415 (2000)","journal-title":"Combinatorica"},{"issue":"1","key":"17_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/S0895480100376794","volume":"18","author":"V. Guruswami","year":"2004","unstructured":"Guruswami, V., Khanna, S.: On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discrete Math.\u00a018(1), 30\u201340 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"17_CR12","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1137\/07068062X","volume":"39","author":"I. Dinur","year":"2009","unstructured":"Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. SIAM J. Comput.\u00a039(3), 843\u2013873 (2009)","journal-title":"SIAM J. Comput."},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-15369-3_11","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"I. Dinur","year":"2010","unstructured":"Dinur, I., Shinkar, I.: On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 138\u2013151. Springer, Heidelberg (2010)"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. In: SODA, pp. 1615\u20131626 (2011)","DOI":"10.1137\/1.9781611973082.125"},{"issue":"1","key":"17_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2005.v001a007","volume":"1","author":"J. H\u00e5stad","year":"2005","unstructured":"H\u00e5stad, J., Khot, S.: Query efficient PCPs with perfect completeness. Theory of Computing\u00a01(1), 119\u2013148 (2005)","journal-title":"Theory of Computing"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: STOC, pp. 191\u2013199 (2000)","DOI":"10.1145\/335305.335329"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Chan, S.O.: Approximation resistance from pairwise independent subgroups. In: STOC, pp. 447\u2013456 (2013)","DOI":"10.1145\/2488608.2488665"},{"key":"17_CR18","first-page":"110","volume":"19","author":"S.O. Chan","year":"2012","unstructured":"Chan, S.O.: Approximation resistance from pairwise independent subgroups. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 110 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/070681612","volume":"39","author":"A. Samorodnitsky","year":"2009","unstructured":"Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput.\u00a039(1), 323\u2013360 (2009)","journal-title":"SIAM J. Comput."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Hast, G.: Beating a random assignment. PhD Thesis (2005)","DOI":"10.1007\/11538462_12"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Dinur, I., Khot, S., Perkins, W., Safra, M.: Hardness of finding independent sets in almost 3-colorable graphs. In: FOCS, pp. 212\u2013221 (2010)","DOI":"10.1109\/FOCS.2010.84"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: Hardness of finding independent sets in almost q-colorable graphs. In: FOCS, pp. 380\u2013389 (2012)","DOI":"10.1109\/FOCS.2012.75"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: STOC, pp. 453\u2013461 (2001)","DOI":"10.1145\/380752.380839"},{"issue":"3","key":"17_CR24","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"17_CR25","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"17_CR26","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput.\u00a027(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"17_CR27","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"issue":"1-2","key":"17_CR28","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0304-3975(97)00226-0","volume":"225","author":"A.E.F. Clementi","year":"1999","unstructured":"Clementi, A.E.F., Trevisan, L.: Improved non-approximability results for minimum vertex cover with density constraints. Theor. Comput. Sci.\u00a0225(1-2), 113\u2013128 (1999)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:51:02Z","timestamp":1558029062000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}