{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T22:10:02Z","timestamp":1740521402327,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228493"},{"type":"electronic","value":"9783540278368"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_34","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"383-395","source":"Crossref","is-referenced-by-count":8,"title":["Coloring Semirandom Graphs Optimally"],"prefix":"10.1007","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"34_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":"34_CR2","doi-asserted-by":"crossref","unstructured":"Beier, R., V\u00f6cking, B.: Random Knapsack in expected polynomial time. Proc. 35th STOC, pp. 232\u2013241 (2003)","DOI":"10.1145\/780542.780578"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A. Blum","year":"1995","unstructured":"Blum, A., Spencer, J.: Coloring random and semirandom k-colorable graphs. J. of Algorithms\u00a019, 203\u2013234 (1995)","journal-title":"J. of Algorithms"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Boppana, R.: Eigenvalues and graph bisection: An average-case analysis. Proc. 28th FOCS, pp. 280\u2013285 (1987)","DOI":"10.1109\/SFCS.1987.22"},{"key":"34_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-45726-7_12","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"A. Coja-Oghlan","year":"2002","unstructured":"Coja-Oghlan, A.: Finding sparse induced subgraphs of semirandom graphs. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 139\u2013148. Springer, Heidelberg (2002)"},{"key":"34_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45061-0_18","volume-title":"Automata, Languages and Programming","author":"A. Coja-Oghlan","year":"2003","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: MAX k-CUT and approximating the chromatic number of random graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 200\u2013211. Springer, Heidelberg (2003)"},{"key":"34_CR7","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":"34_CR8","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/S0304-3975(02)00535-2","volume":"299","author":"L. Engebretsen","year":"2003","unstructured":"Engebretsen, L., Holmerin, J.: Towards optimal lower bounds for clique and chromatic number. TCS\u00a0299, 537\u2013584 (2003)","journal-title":"TCS"},{"key":"34_CR9","first-page":"639","volume":"63","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kilian, J.: Heuristics for semirandom graph problems. JCSS\u00a063, 639\u2013671 (2001)","journal-title":"JCSS"},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A","volume":"16","author":"U. Feige","year":"2000","unstructured":"Feige, U., Krauthgamer, J.: Finding and certifying a large hidden clique in a semirandom graph. Random Structures & Algorithms\u00a016, 195\u2013208 (2000)","journal-title":"Random Structures & Algorithms"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF02523688","volume":"18","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica\u00a018, 61\u201377 (1997)","journal-title":"Algorithmica"},{"key":"34_CR12","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":"34_CR13","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":"34_CR14","doi-asserted-by":"crossref","unstructured":"Krivelevich, M.: Coloring random graphs \u2013 an algorithmic perspective. In: Proc. 2nd MathInfo, pp. 175\u2013195 (2002)","DOI":"10.1007\/978-3-0348-8211-8_11"},{"key":"34_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/3-540-08442-8_114","volume-title":"Fundamentals of Computation Theory","author":"L. Ku\u010dera","year":"1977","unstructured":"Ku\u010dera, L.: Expected behavior of graph coloring algorithms. In: Karpinski, M. (ed.) FCT 1977. LNCS, vol.\u00a056, pp. 447\u2013451. Springer, Heidelberg (1977)"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(89)90200-7","volume":"30","author":"L. Ku\u010dera","year":"1989","unstructured":"Ku\u010dera, L.: Graphs with small chromatic number are easy to color. Information Processing Letters\u00a030, 233\u2013236 (1989)","journal-title":"Information Processing Letters"},{"key":"34_CR17","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":"34_CR18","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jagm.1999.1035","volume":"33","author":"C.R. Subramanian","year":"1999","unstructured":"Subramanian, C.R.: Minimum coloring random and semirandom graphs in polynomial average time. J. of Algorithms\u00a033, 112\u2013123 (1999)","journal-title":"J. of Algorithms"},{"key":"34_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/3-540-45253-2_38","volume-title":"Algorithms - ESA 2000","author":"C.R. Subramanian","year":"2000","unstructured":"Subramanian, C.R.: Coloring sparse random graphs in polynomial average time. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 415\u2013426. Springer, Heidelberg (2000)"},{"key":"34_CR20","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","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T21:30:29Z","timestamp":1740519029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}