{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:48:39Z","timestamp":1725853719276},"publisher-location":"New York, NY","reference-count":23,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_170","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:15:58Z","timestamp":1553098558000},"page":"869-872","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graph Coloring"],"prefix":"10.1007","author":[{"given":"Michael","family":"Langberg","sequence":"first","affiliation":[]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"3","key":"159_CR7245","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A Blum","year":"1994","unstructured":"Blum A (1994) New approximations for graph coloring. J ACM 41(3):470\u2013516","journal-title":"J ACM"},{"issue":"6","key":"159_CR7246","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 (1997) An \n                  \n                    \n                      \u00d5\n                      (\n                      \n                        \n                          n\n                        \n                        \n                          3\n                          \u2215\n                          14\n                        \n                      \n                      )\n                    \n                  \n                  $$\\tilde{O}(n^{3\/14})$$\n                -coloring for 3-colorable graphs. Inf Process Lett 61(6):49\u201353","journal-title":"Inf Process Lett"},{"key":"159_CR7247","doi-asserted-by":"crossref","unstructured":"Chaitin GJ (1982) Register allocation & spilling via graph coloring. In: Proceedings of the 1982 SIGPLAN symposium on compiler construction, pp\u00a098\u2013105","DOI":"10.1145\/800230.806984"},{"key":"159_CR7248","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"GJ Chaitin","year":"1981","unstructured":"Chaitin GJ, Auslander MA, Chandra AK, Cocke J, Hopkins ME, Markstein PW (1981) Register allocation via coloring. Comput Lang 6:47\u201357","journal-title":"Comput Lang"},{"key":"159_CR7249","doi-asserted-by":"crossref","unstructured":"Chlamtac E (2007) Approximation algorithms using hierarchies of semidefinite programming relaxations. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science, pp\u00a0691\u2013701","DOI":"10.1109\/FOCS.2007.72"},{"issue":"3","key":"159_CR7250","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 (2009) Conditional hardness for approximate coloring. SIAM J Comput 39(3):843\u2013873","journal-title":"SIAM J Comput"},{"issue":"1","key":"159_CR7251","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01196133","volume":"17","author":"U Feige","year":"1997","unstructured":"Feige U (1997) Randomized graph products, chromatic numbers, and the Lov\u00e1sz theta function. Combinatorica 17(1):79\u201390","journal-title":"Combinatorica"},{"issue":"2","key":"159_CR7252","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U Feige","year":"2004","unstructured":"Feige U (2004) Approximating maximum clique by removing subgraphs. SIAM J Discret Math 18(2):219\u2013225","journal-title":"SIAM J Discret Math"},{"key":"159_CR7253","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U Feige","year":"1998","unstructured":"Feige U, Kilian J (1998) Zero knowledge and the chromatic number. J Comput Syst Sci 57:187\u2013199","journal-title":"J Comput Syst Sci"},{"issue":"6","key":"159_CR7254","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539703431391","volume":"33","author":"U Feige","year":"2004","unstructured":"Feige U, Langberg M, Schechtman G (2004) Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM J Comput 33(6):1338\u20131368","journal-title":"SIAM J Comput"},{"key":"159_CR7255","doi-asserted-by":"crossref","unstructured":"Guruswami V, Khanna S (2000) On the hardness of 4-coloring a 3-colorable graph. In: Proceedings of the 15th annual IEEE conference on computational complexity, pp\u00a0188\u2013197","DOI":"10.1109\/CCC.2000.856749"},{"key":"159_CR7256","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M Halldorsson","year":"1993","unstructured":"Halldorsson M (1993) A still better performance guarantee for approximate graph coloring. Inf Process Lett 45:19\u201323","journal-title":"Inf Process Lett"},{"key":"159_CR7257","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/S0196-6774(02)00217-1","volume":"45","author":"E Halperin","year":"2002","unstructured":"Halperin E, Nathaniel R, Zwick U (2002) Coloring k-colorable graphs using smaller palettes. J Algorithms 45:72\u201390","journal-title":"J Algorithms"},{"issue":"1","key":"159_CR7258","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J (1999) Clique is hard to approximate within \n                  \n                    \n                      \n                        \n                          n\n                        \n                        \n                          1\n                          \u2212\n                          \ud835\udf00\n                        \n                      \n                    \n                  \n                  $$n^{1-\\varepsilon }$$\n                . Acta Math 182(1):105\u2013142","journal-title":"Acta Math"},{"key":"159_CR7259","doi-asserted-by":"crossref","unstructured":"Kawarabayashi K, Thorup M (2012) Combinatorial coloring of 3-Colorable graphs. In: Proceedings of the 53rd annual IEEE symposium on foundations of computer science, pp\u00a068\u201375","DOI":"10.1109\/FOCS.2012.16"},{"key":"159_CR7260","unstructured":"Kawarabayashi K, Thorup M (2014) Coloring 3-colorable graphs with o(n1\u22155) colors. In: Proceedings of the 31st international symposium on theoretical aspects of computer science, pp\u00a0458\u2013469"},{"issue":"2","key":"159_CR7261","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D Karger","year":"1998","unstructured":"Karger D, Motwani R, Sudan M (1998) Approximate graph coloring by semidefinite programming. J ACM 45(2):246\u2013265","journal-title":"J ACM"},{"key":"159_CR7262","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 (2000) On the hardness of approximating the chromatic number. Combinatorica 20:393\u2013415","journal-title":"Combinatorica"},{"key":"159_CR7263","doi-asserted-by":"crossref","unstructured":"Khot S (2001) Improved inapproximability results for max clique, chromatic number and approximate graph coloring. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science, pp\u00a0600\u2013609","DOI":"10.1109\/SFCS.2001.959936"},{"key":"159_CR7264","unstructured":"Khot S (2002) On the power of unique 2-prover 1-round games. In: Proceedings of the 34th annual ACM symposium on theory of computing, pp\u00a0767\u2013775"},{"key":"159_CR7265","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz L (1979) On the Shannon capacity of a graph. IEEE Trans Inf Theory 25:2\u201313","journal-title":"IEEE Trans Inf Theory"},{"issue":"4","key":"159_CR7266","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A Wigderson","year":"1983","unstructured":"Wigderson A (1983) Improving the performance guarantee for approximate graph coloring. J ACM 30(4):729\u2013735","journal-title":"J ACM"},{"key":"159_CR7267","doi-asserted-by":"crossref","unstructured":"Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th annual ACM symposium on theory of computing, pp\u00a0681\u2013690","DOI":"10.1145\/1132516.1132612"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T17:37:12Z","timestamp":1553103432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_170","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}