{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:31Z","timestamp":1725511771701},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_11","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"121-132","source":"Crossref","is-referenced-by-count":3,"title":["Why Almost All k-Colorable Graphs Are Easy"],"prefix":"10.1007","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","reference":[{"issue":"1","key":"11_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., Friedgut, E.: A sharp threshold for k-colorability. Random Struct. Algorithms\u00a014(1), 63\u201370 (1999)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"11_CR2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.37236\/1461","volume":"6","author":"D. Achlioptas","year":"1999","unstructured":"Achlioptas, D., Molloy, M.: Almost all graphs with 2.522n edges are not 3-colorable. Elec. Jour. Of Comb.\u00a06(1), R29 (1999)","journal-title":"Elec. Jour. Of Comb."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Moore, C.: Almost all graphs with average degree 4 are 3-colorable. In: STOC \u201902, pp. 199\u2013208 (2002)","DOI":"10.1145\/509907.509940"},{"issue":"6","key":"11_CR4","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. on Comput.\u00a026(6), 1733\u20131748 (1997)","journal-title":"SIAM J. on Comput."},{"key":"11_CR5","unstructured":"Ben-Sasson, E., Bilu, Y., Gutfreund, D.: Finding a randomly planted assignment in a random 3CNF. Manuscript (2002)"},{"issue":"2","key":"11_CR6","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A. Blum","year":"1995","unstructured":"Blum, A., Spencer, J.: Coloring random and semi-random k-colorable graphs. J. of Algorithms\u00a019(2), 204\u2013234 (1995)","journal-title":"J. of Algorithms"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B. Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B.: The chromatic number of random graphs. Combin.\u00a08(1), 49\u201355 (1988)","journal-title":"Combin."},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, J.: Coloring sparse random k-colorable graphs in polynomial expected time. In: Proc. 30th MFCS, pp. 156\u2013167 (2005)","DOI":"10.1007\/11549345_15"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Braunstein, A., et al.: Constraint satisfaction by survey propagation. In: Computational Complexity and Statistical Physics (2005)","DOI":"10.1093\/oso\/9780195177374.003.0011"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Chen, H.: An algorithm for sat above the threshold. In: 6th International Conference on Theory and Applications of Satisfiability Testing, pp. 14\u201324 (2003)","DOI":"10.1007\/978-3-540-24605-3_2"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/978-3-540-27836-8_34","volume-title":"Automata, Languages and Programming","author":"A. Coja-Oghlan","year":"2004","unstructured":"Coja-Oghlan, A.: Coloring semirandom graphs optimally. In: D\u00edaz, J., et al. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 383\u2013395. Springer, Heidelberg (2004)"},{"issue":"4","key":"11_CR12","doi-asserted-by":"publisher","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. Algorithms\u00a010(4), 451\u2013489 (1989)","journal-title":"J. Algorithms"},{"issue":"2","key":"11_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. and Syst. Sci.\u00a057(2), 187\u2013199 (1998)","journal-title":"J. Comput. and Syst. Sci."},{"issue":"4","key":"11_CR14","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 Syst. Sci.\u00a063(4), 639\u2013671 (2001)","journal-title":"J. Comput. and Syst. Sci."},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Feige, U., Mossel, E., Vilenchik, D.: Complete convergence of message passing algorithms for some satisfiability problems. In: RANDOM, pp. 339\u2013350 (2006)","DOI":"10.1007\/11830924_32"},{"key":"11_CR16","first-page":"357","volume-title":"Proc. 14th ACM-SIAM Symp. on Discrete Algorithms","author":"A. Flaxman","year":"2003","unstructured":"Flaxman, A.: A spectral technique for random satisfiable 3CNF formulas. In: Proc. 14th ACM-SIAM Symp. on Discrete Algorithms, pp. 357\u2013363. ACM Press, New York (2003)"},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"67","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(1), 67\u201381 (1997)","journal-title":"Algorithmica"},{"key":"11_CR18","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, 2nd edn. Algorithms and Combinatorics, vol.\u00a02. Springer, Berlin (1993)","edition":"2"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Vilenchik, D.: Semirandom models as benchmarks for coloring algorithms. In: ANALCO, pp. 211\u2013221 (2006)","DOI":"10.1137\/1.9781611972962.4"},{"key":"11_CR20","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)"},{"issue":"1","key":"11_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T. \u0141uczak","year":"1991","unstructured":"\u0141uczak, T.: The chromatic number of random graphs. Combin.\u00a011(1), 45\u201354 (1991)","journal-title":"Combin."},{"issue":"26","key":"11_CR22","doi-asserted-by":"publisher","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","volume":"89","author":"R. Mulet","year":"2002","unstructured":"Mulet, R., et al.: Coloring random graphs. Phys. Rev. Lett.\u00a089(26), 268701 (2002)","journal-title":"Phys. Rev. Lett."},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1002\/rsa.3240060104","volume":"6","author":"H. Pr\u00f6mel","year":"1995","unstructured":"Pr\u00f6mel, H., Steger, A.: Random l-colorable graphs. Random Structures and Algorithms\u00a06, 21\u201337 (1995)","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","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. Algorithms\u00a09(1), 63\u201382 (1988)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T19:33:41Z","timestamp":1683833621000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_11","relation":{},"subject":[]}}