{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T16:52:05Z","timestamp":1763830325146},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,8,4]],"date-time":"2009-08-04T00:00:00Z","timestamp":1249344000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00224-009-9231-5","type":"journal-article","created":{"date-parts":[[2009,8,3]],"date-time":"2009-08-03T15:55:25Z","timestamp":1249314925000},"page":"523-565","source":"Crossref","is-referenced-by-count":5,"title":["Why Almost All k-Colorable Graphs Are Easy to Color"],"prefix":"10.1007","volume":"46","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Vilenchik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,8,4]]},"reference":[{"issue":"1","key":"9231_CR1","doi-asserted-by":"crossref","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,\u00a0D., Friedgut,\u00a0E.: A sharp threshold for k-colorability. Random Struct. Algorithms 14(1), 63\u201370 (1999)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"9231_CR2","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/S0097539703434231","volume":"36","author":"D. Achlioptas","year":"2006","unstructured":"Achlioptas,\u00a0D., Moore,\u00a0C.: Random k-sat: Two moments suffice to cross a sharp threshold. SIAM J. Comput. 36(3), 740\u2013762 (2006)","journal-title":"SIAM J. Comput."},{"key":"9231_CR3","doi-asserted-by":"crossref","unstructured":"Achlioptas,\u00a0D., Ricci-Tersenghi,\u00a0F.: On the solution-space geometry of random constraint satisfaction problems. In: Proc. 38th ACM Symp. on Theory of Computing","DOI":"10.1145\/1132516.1132537"},{"issue":"6","key":"9231_CR4","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon,\u00a0N., Kahale,\u00a0N.: A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput. 26(6), 1733\u20131748 (1997)","journal-title":"SIAM J. Comput."},{"key":"9231_CR5","unstructured":"Ben-Shimon,\u00a0S., Krivelevich,\u00a0M.: Random regular graphs of non-constant degree: edge distribution and applications. Manuscript (2006)"},{"issue":"2","key":"9231_CR6","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A. Blum","year":"1995","unstructured":"Blum,\u00a0A., Spencer,\u00a0J.: Coloring random and semi-random k-colorable graphs. J.\u00a0Algorithms 19(2), 204\u2013234 (1995)","journal-title":"J.\u00a0Algorithms"},{"issue":"1","key":"9231_CR7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B. Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s,\u00a0B.: The chromatic number of random graphs. Combinatorica 8(1), 49\u201355 (1988)","journal-title":"Combinatorica"},{"key":"9231_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher,\u00a0J.: Coloring sparse random k-colorable graphs in polynomial expected time. In: Proc. 30th International Symp. on Mathematical Foundations of Computer Science, pp. 156\u2013167 (2005)","DOI":"10.1007\/11549345_15"},{"key":"9231_CR9","doi-asserted-by":"crossref","unstructured":"Braunstein,\u00a0A., M\u00e9zard,\u00a0M., Weigt,\u00a0M., Zecchina,\u00a0R.: Constraint satisfaction by survey propagation. Comput. Complex. Stat. Phys. (2005)","DOI":"10.1093\/oso\/9780195177374.003.0011"},{"key":"9231_CR10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A. Braunstein","year":"2005","unstructured":"Braunstein,\u00a0A., Mezard,\u00a0M., Zecchina,\u00a0R.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27, 201\u2013226 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"9231_CR11","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan,\u00a0A.: Coloring semirandom graphs optimally. In: Proc. 31st International Colloquium on Automata, Languages, and Programming, pp. 383\u2013395 (2004)","DOI":"10.1007\/978-3-540-27836-8_34"},{"key":"9231_CR12","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan,\u00a0A., Krivelevich,\u00a0M., Vilenchik,\u00a0D.: Why almost all satisfiable k-cnf formulas are easy. In: 13th Conference on Analysis of Algorithms, DMTCS Proceedings, pp. 89\u2013102 (2007)","DOI":"10.46298\/dmtcs.3538"},{"issue":"1\u20133","key":"9231_CR13","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.tcs.2008.01.005","volume":"393","author":"H. Daud\u00e9","year":"2008","unstructured":"Daud\u00e9,\u00a0H., M\u00e9zard,\u00a0M., Mora,\u00a0T., Zecchina,\u00a0R.: Pairs of sat-assignments in random boolean formul\u00e6. Theoret. Comput. Sci. 393(1\u20133), 260\u2013279 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"9231_CR14","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M.E. Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M.: The solution of some random np-hard problems in polynomial expected time. J.\u00a0Algorithms 10(4), 451\u2013489 (1989)","journal-title":"J.\u00a0Algorithms"},{"issue":"2","key":"9231_CR15","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige,\u00a0U., Kilian,\u00a0J.: Zero knowledge and the chromatic number. J.\u00a0Comput. Syst. Sci. 57(2), 187\u2013199 (1998)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"4","key":"9231_CR16","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1006\/jcss.2001.1773","volume":"63","author":"U. Feige","year":"2001","unstructured":"Feige,\u00a0U., Kilian,\u00a0J.: Heuristics for semirandom graph problems. J.\u00a0Comput. Syst. Sci. 63(4), 639\u2013671 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9231_CR17","doi-asserted-by":"crossref","unstructured":"Feige,\u00a0U., Mossel,\u00a0E., Vilenchik,\u00a0D.: Complete convergence of message passing algorithms for some satisfiability problems. In: Random, pp. 339\u2013350 (2006)","DOI":"10.1007\/11830924_32"},{"issue":"2","key":"9231_CR18","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/rsa.20089","volume":"27","author":"U. Feige","year":"2005","unstructured":"Feige,\u00a0U., Ofek,\u00a0E.: Spectral techniques applied to sparse random graphs. Random Struct. Algorithms 27(2), 251\u2013275 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"9231_CR19","doi-asserted-by":"crossref","unstructured":"Friedman,\u00a0J., Kahn,\u00a0J., Szemer\u00e9di,\u00a0E.: On the second eigenvalue in random regular graphs. In: Proc. 21st ACM Symp. on Theory of Computing, pp. 587\u2013598 (1989)","DOI":"10.1145\/73007.73063"},{"key":"9231_CR20","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding,\u00a0W.: Probability inequalities for sums of bounded random variables. J.\u00a0Am. Stat. Assoc. 58, 13\u201330 (1963)","journal-title":"J.\u00a0Am. Stat. Assoc."},{"key":"9231_CR21","doi-asserted-by":"crossref","unstructured":"Krivelevich,\u00a0M., Vilenchik,\u00a0D.: Semirandom models as benchmarks for coloring algorithms. In: 3rd Workshop on Analytic Algorithmics and Combinatorics, pp. 211\u2013221 (2006)","DOI":"10.1137\/1.9781611972962.4"},{"key":"9231_CR22","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/3-540-08442-8_114","volume-title":"Proc. Fundamentals of Computation Theory","author":"L. Ku\u010dera","year":"1977","unstructured":"Ku\u010dera,\u00a0L.: Expected behavior of graph coloring algorithms. In: Proc. Fundamentals of Computation Theory. Lecture Notes in Comput. Sci., vol.\u00a056, pp. 447\u2013451. Springer, Berlin (1977)"},{"issue":"1","key":"9231_CR23","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T. \u0141uczak","year":"1991","unstructured":"\u0141uczak,\u00a0T.: The chromatic number of random graphs. Combinatorica 11(1), 45\u201354 (1991)","journal-title":"Combinatorica"},{"issue":"26","key":"9231_CR24","doi-asserted-by":"crossref","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","volume":"89","author":"R. Mulet","year":"2002","unstructured":"Mulet,\u00a0R., Pagnani,\u00a0A., Weigt,\u00a0M., Zecchina,\u00a0R.: Coloring random graphs. Phys. Rev. Lett. 89(26), 268701 (2002)","journal-title":"Phys. Rev. Lett."},{"key":"9231_CR25","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/rsa.3240060104","volume":"6","author":"H. Pr\u00f6mel","year":"1995","unstructured":"Pr\u00f6mel,\u00a0H., Steger,\u00a0A.: Random l-colorable graphs. Random Struct. Algorithms 6, 21\u201337 (1995)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"9231_CR26","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0196-6774(88)90005-3","volume":"9","author":"J.S. Turner","year":"1988","unstructured":"Turner, J.S.: Almost all k-colorable graphs are easy to color. J.\u00a0Algorithms 9(1), 63\u201382 (1988)","journal-title":"J.\u00a0Algorithms"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9231-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9231-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9231-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,9]],"date-time":"2021-10-09T08:32:51Z","timestamp":1633768371000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9231-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,4]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9231"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9231-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,4]]}}}