{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:43:22Z","timestamp":1742388202344,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_18","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"200-211","source":"Crossref","is-referenced-by-count":14,"title":["MAX k-CUT and Approximating the Chromatic Number of Random Graphs"],"prefix":"10.1007","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[]},{"given":"Vishal","family":"Sanwalani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","volume":"14","author":"D. Achlioptas","year":"1999","unstructured":"Achlioptas, D. and Friedgut, E.: A sharp threshold for k-colorability. Random Structures & Algorithms 14 (1999) 63\u201370.","journal-title":"Random Structures & Algorithms"},{"key":"18_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0024489","volume-title":"An upper bound for the maximum cut mean value","author":"A. Bertoni","year":"1997","unstructured":"Bertoni, A., Campadelli, P., Posenato, R.: An upper bound for the maximum cut mean value. Springer LNCS 1335 (1997) 78\u201384"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A. and Taraz, A.: Colouring random graphs in expected polynomial time. Proc. 20th STACS (2003) 487\u2013498","DOI":"10.1007\/3-540-36494-3_43"},{"key":"18_CR4","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M., Sorkin, G.B.: Random MAX SAT, random MAX CUT, and their phase transitions. Proc. 14th SODA (2003) 329\u2013337"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C. Delorme","year":"1993","unstructured":"Delorme, C. and Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Programming 62 (1993) 557\u2013574.","journal-title":"Math. Programming"},{"key":"18_CR6","unstructured":"Feige, U. and Kilian, J.: Zero knowledge and the chromatic number. Proc. 11th IEEE Conf. Comput. Complexity (1996) 278\u2013287."},{"key":"18_CR7","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs, report MCS03-01, Weizmann Institute of Science (2003)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Friedman, J., Kahn, J., Szemeredi, E.: On the second eigenvalue in random regular graphs. Proc. 21st ACM Symp. Theory of Computing (STOC) (1989) 587\u2013598.","DOI":"10.1145\/73007.73063"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF02523688","volume":"18","author":"A. Frieze","year":"1997","unstructured":"Frieze, A. and Jerrum, M.: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18 (1997) 61\u201377.","journal-title":"Algorithmica"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"Frieze, A. and McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms 10 (1997) 5\u201342.","journal-title":"Random Structures and Algorithms"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z. and Komlo\u015b, J.: The eigenvalues of random symmetric matrices. Combinatorica 1 (1981) 233\u2013241.","journal-title":"Combinatorica"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X. and Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. of the ACM 42 (1995) 1115\u20131145.","journal-title":"J. of the ACM"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Goemans, M.X. and Williamson, D.P.: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Proc. 33rd ACM Symp. Theory of Computing (STOC) 2001, 443\u2013452.","DOI":"10.1145\/380752.380838"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Goerdt, A. and Jurdzinski, A.: Some results on random unsatisfiable k-Sat instances and approximation algorithms applied to random structures. Proc. Mathematical Foundations of Computer Science (MFCS) 2002, 280\u2013291.","DOI":"10.1007\/3-540-45687-2_23"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Proc. 29th ACM Symp. Theory of Computing (STOC) 1997, 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs, Wiley 2000.","DOI":"10.1002\/9781118032718"},{"key":"18_CR18","unstructured":"Kalapala, V. and Moore, C.: MAX-CUT on sparse random graphs. University of New Mexico Technical Report TR-CS-2002-24."},{"key":"18_CR19","unstructured":"Karp, R.: The probabilistic analysis of combinatorial optimization algorithms. Proc. Intl. Congress of Mathematicians (1984) 1601\u20131609."},{"key":"18_CR20","unstructured":"Kinnison, Robert: Applied Extreme Value Statistics. Battele Press. (1985) 54\u201357."},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1013899527204","volume":"6","author":"M. Krivelevich","year":"2002","unstructured":"Krivelevich, M., Vu, V.H.: Approximating the independence number and the chromatic number in expected polynomial time. J. Combin. Opt. 6 (2002) 143\u2013155.","journal-title":"J. Combin. Opt."},{"key":"18_CR22","unstructured":"Krivelevich, M.: Coloring random graphs \u2014 an algorithmic perspective. Proc. 2nd Coll. on Math. and Comp. Sci., B. Chauvin et al. eds., Birkh\u00e4user (2002) 175\u2013195."},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Information Processing Letters 5 (1976) 66\u201367.","journal-title":"Information Processing Letters"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Levin, L.: Average case complete problems. Proc. 16th STOC (1984) 465","DOI":"10.1145\/800057.808713"},{"issue":"4","key":"18_CR25","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF01275671","volume":"11","author":"B. D. McKay","year":"1991","unstructured":"McKay, B. D. and Wormald, N. C.: Asymptotic enumeration by degree sequence of graphs with degrees o(n 1\/2). Combinatorica 11(4) (1991) 369\u2013382.","journal-title":"Combinatorica"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0805024","volume":"5","author":"S. Poljak","year":"1995","unstructured":"Poljak, S. and Rendl, F.: Nonpolyhedral relaxations of graph-bisection problems. SIAM J. Optimization 5 (1995) 467\u2013487.","journal-title":"SIAM J. Optimization"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:43:48Z","timestamp":1737287028000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}