{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T13:56:35Z","timestamp":1765806995489},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_1","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T05:20:39Z","timestamp":1313126439000},"page":"1-12","source":"Crossref","is-referenced-by-count":8,"title":["New Tools for Graph Coloring"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[]},{"given":"Rong","family":"Ge","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/FOCS.2010.59","volume-title":"Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010","author":"S. Arora","year":"2010","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 563\u2013572. IEEE Computer Society, Washington, DC, USA (2010)"},{"key":"1_CR2","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., Charikar, M.: 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":"1_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation (2011)","DOI":"10.1109\/FOCS.2011.95"},{"key":"1_CR4","first-page":"15","volume-title":"Combinatorial Mathematics and its Applications","author":"N.L. Biggs","year":"1971","unstructured":"Biggs, N.L.: Intersection matrices for linear graphs. In: Welsh, D.J.A. (ed.) Combinatorial Mathematics and its Applications, pp. 15\u201323. Academic Press, London (1971)"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A. Blum","year":"1994","unstructured":"Blum, A.: New approximation algorithms for graph coloring. J. ACM\u00a041, 470\u2013516 (1994)","journal-title":"J. ACM"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A. Blum","year":"1996","unstructured":"Blum, A., Karger, D.: An $\\tilde{O}(n^{3\/14})$ -coloring algorithm for 3-colorable graphs. Information Processing Letters\u00a061, 49\u201353 (1996)","journal-title":"Information Processing Letters"},{"key":"1_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74341-2","volume-title":"Distance Regular Graphs","author":"A.E. Brouwer","year":"1989","unstructured":"Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance Regular Graphs. Springer, Heidelberg (1989)"},{"key":"1_CR8","unstructured":"Chlamtac, E.: Non-Local Analysis of SDP-Based Approximation Algorithms. PhD thesis, Princeton University (2009)"},{"key":"1_CR9","unstructured":"Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. Unpublished manuscript"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1145\/1132516.1132567","volume-title":"Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006","author":"I. Dinur","year":"2006","unstructured":"Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 344\u2013353. ACM, New York (2006)"},{"key":"1_CR11","first-page":"283","volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002","author":"U. Feige","year":"2002","unstructured":"Feige, U., Langberg, M., Schechtman, G.: Graphs with tiny vector chromatic numbers and huge chromatic numbers. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002, pp. 283\u2013292. IEEE Computer Society, Washington, DC, USA (2002)"},{"issue":"1","key":"1_CR12","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1090\/S0002-9947-1987-0871675-6","volume":"300","author":"P. Frankl","year":"1987","unstructured":"Frankl, P., Rodl, V.: Forbidden intersections. Transactions of the American Mathematical Society\u00a0300(1), 259\u2013286 (1987)","journal-title":"Transactions of the American Mathematical Society"},{"key":"1_CR13","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.: Approximate graph coloring by semidefinite programming. J. ACM\u00a045, 246\u2013265 (1998)","journal-title":"J. ACM"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 293\u2013303. Springer, Heidelberg (2001)"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M. Laurent","year":"2001","unstructured":"Laurent, M.: A comparison of the sherali-adams, lovasz-schrijver and lasserre relaxations for 0-1 programming. Mathematics of Operations Research\u00a028, 470\u2013496 (2001)","journal-title":"Mathematics of Operations Research"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization\u00a01, 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxation between the continuous and convex hull representations. SIAM J. Discret. Math.\u00a03, 411\u2013430 (1990)","journal-title":"SIAM J. Discret. Math."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1109\/SFCS.1994.365707","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science","author":"M. Szegedy","year":"1994","unstructured":"Szegedy, M.: A note on the \u03b8 number of lovasz and the generalized delsarte bound. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 36\u201339. IEEE Computer Society, Washington, DC, USA (1994)"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"Wigderson, A.: Improving the performance guarantee for approximate graph coloring. J. ACM\u00a030, 729\u2013735 (1983)","journal-title":"J. ACM"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/1132516.1132612","volume-title":"Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006","author":"D. Zuckerman","year":"2006","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 681\u2013690. ACM, New York (2006)"}],"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-22935-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T21:03:06Z","timestamp":1560459786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}