{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:18Z","timestamp":1763467998029,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407706"},{"type":"electronic","value":"9783540451983"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_20","type":"book-chapter","created":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T03:32:30Z","timestamp":1294457550000},"page":"228-239","source":"Crossref","is-referenced-by-count":2,"title":["The Lov\u00e1sz Number of Random Graphs"],"prefix":"10.1007","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput.\u00a026, 1733\u20131748 (1997)","journal-title":"SIAM J. Comput."},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Krivelevich, M.: The concentration of the chromatic number of random graphs. Combinatorica\u00a017, 303\u2013313","DOI":"10.1007\/BF01215914"},{"key":"20_CR3","unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: Proc. 13th SODA, pp. 616\u2013620 (2002)"},{"key":"#cr-split#-20_CR4.1","unstructured":"Coja-Oghlan, A., Taraz, A.: Exact and approximative algorithms for colouring G(n, p) (preprint), available from http:\/\/www.informatik.hu-berlin.de\/~coja\/;"},{"key":"#cr-split#-20_CR4.2","unstructured":"A preliminary version has appeard in Proc. 20th STACS (2003), pp. 487\u2013498 (2003)"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/3-540-36494-3_45","volume-title":"STACS 2003","author":"A. Coja-Oghlan","year":"2003","unstructured":"Coja-Oghlan, A.: Finding large independent sets in polynomial expected time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 511\u2013522. Springer, Heidelberg (2003)"},{"key":"#cr-split#-20_CR6.1","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: MAX k-CUT and approximating the chromatic number of random graphs, available from http:\/\/www.informatik.huberlin.de\/~coja\/;"},{"key":"#cr-split#-20_CR6.2","unstructured":"An extended abstract version has appeared in Proc. ICALP 2003 (2003)"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Feige, U.: Randomized graph products, chromatic numbers, and the Lov\u00e1sz theta function. Combinatorica\u00a017(1), 79\u201390","DOI":"10.1007\/BF01196133"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1006\/jcss.2001.1773","volume":"63","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kilian, J.: Heuristics for semirandom graph problems. J. Comput. and System Sci.\u00a063, 639\u2013671 (2001)","journal-title":"J. Comput. and System Sci."},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. In: Proc. 11th IEEE Conf. Comput. Complexity, pp. 278\u2013287 (1996)","DOI":"10.1109\/CCC.1996.507690"},{"key":"20_CR10","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs, report MCS03-01, Weizmann Institute (2003), available from http:\/\/www.wisdom.weizmann.ac.il\/math\/research.shtml"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Friedman, J., Kahn, J., Szemeredi, E.: On the second eigenvalue in random regular graphs. In: Proc. 21st STOC, pp. 587\u2013598 (1989)","DOI":"10.1145\/73007.73063"},{"key":"20_CR12","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., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures & Algorithms\u00a010, 5\u201342 (1997)","journal-title":"Random Structures & Algorithms"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z., Komlo\u015b, J.: The eigenvalues of random symmetric matrices. Combinatorica\u00a01, 233\u2013241 (1981)","journal-title":"Combinatorica"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480195294994","volume":"11","author":"M.X. Goemans","year":"1998","unstructured":"Goemans, M.X., Kleinberg, J.: The Lovasz theta function and a semidefinite programming relaxation of vertex cover. SIAM J. on Discrete Math.\u00a011, 1\u201348 (1998)","journal-title":"SIAM J. on Discrete Math."},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfyability problems using semidefinite programming. J. ACM\u00a042, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"20_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization.","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, Heidelberg (1988)"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n1\u2009\u2212\u2009\u03b5 . In: Proc. 37th FOCS, pp. 627\u2013636 (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"key":"20_CR18","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley, Chichester (2000)"},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02579314","volume":"2","author":"F. Juh\u00e1sz","year":"1982","unstructured":"Juh\u00e1sz, F.: The asymptotic behaviour of Lov\u00e1sz \u03d1 function for random graphs. Combinatorica\u00a02, 269\u2013270 (1982)","journal-title":"Combinatorica"},{"key":"20_CR20","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":"20_CR21","doi-asserted-by":"crossref","unstructured":"Knuth, D.: The sandwich theorem. Electron. J. Combin.\u00a01 (1994)","DOI":"10.37236\/1193"},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(01)00187-9","volume":"81","author":"M. Krivelevich","year":"2002","unstructured":"Krivelevich, M.: Deciding k-colorability in expected polynomial time. Information Processing Letters\u00a081, 1\u20136 (2002)","journal-title":"Information Processing Letters"},{"key":"20_CR23","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. of Combinatorial Optimization\u00a06, 143\u2013155 (2002)","journal-title":"J. of Combinatorial Optimization"},{"key":"20_CR24","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\u00a05, 66\u201367 (1976)","journal-title":"Information Processing Letters"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T. \u0141uczak","year":"1991","unstructured":"\u0141uczak, T.: A note on the sharp concentration of the chromatic number of random graphs. Combinatorica\u00a011, 45\u201354 (1991)","journal-title":"Combinatorica"},{"key":"20_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02579208","volume":"7","author":"E. Shamir","year":"1987","unstructured":"Shamir, E., Spencer, J.: Sharp concentration of the chromatic number of random graphs G n,p . Combinatorica\u00a07, 121\u2013129 (1987)","journal-title":"Combinatorica"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: A note on the \u03b8 number of Lov\u00e1sz and the generalized Delsarte bound. In: Proc. 35th FOCS, pp. 36\u201339 (1994)","DOI":"10.1109\/SFCS.1994.365707"}],"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-540-45198-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T14:52:28Z","timestamp":1740840748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}