{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:36:48Z","timestamp":1750469808666},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540287025"},{"type":"electronic","value":"9783540318675"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549345_15","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:05:47Z","timestamp":1127815547000},"page":"156-167","source":"Crossref","is-referenced-by-count":4,"title":["Coloring Sparse Random k-Colorable Graphs in Polynomial Expected Time"],"prefix":"10.1007","author":[{"given":"Julia","family":"B\u00f6ttcher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"15_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 Journal on Computing\u00a026(6), 1733\u20131748 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: Coloring semirandom graphs optimally. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, pp. 383\u2013395 (2004)","DOI":"10.1007\/978-3-540-27836-8_34"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: MAX k-CUT and approximating the chromatic number of random graphs. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming, pp. 200\u2013211 (2003)","DOI":"10.1007\/3-540-45061-0_18"},{"key":"15_CR4","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. Journal of Algorithms\u00a010, 451\u2013489 (1989)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"15_CR5","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. Journal of Computer and System Sciences\u00a057(2), 187\u2013199 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF02523688","volume":"18","author":"A.M. Frieze","year":"1997","unstructured":"Frieze, A.M., Jerrum, M.: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica\u00a018, 61\u201377 (1997)","journal-title":"Algorithmica"},{"key":"15_CR7","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Company, New York (1979)"},{"key":"15_CR8","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. Springer, Berlin (1993)"},{"issue":"3","key":"15_CR9","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s004930070013","volume":"20","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica\u00a020(3), 393\u2013415 (2000)","journal-title":"Combinatorica"},{"key":"15_CR10","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":"15_CR11","doi-asserted-by":"crossref","unstructured":"Ku\u010dera, L.: Expected behavior of graph colouring algorithms. In: Proceedings of the 1977 International Conference on Fundamentals of Computation Theory, pp. 447\u2013451 (1977)","DOI":"10.1007\/3-540-08442-8_114"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1017\/S0963548399004137","volume":"9","author":"C.R. Subramanian","year":"2000","unstructured":"Subramanian, C.R.: Algorithms for coloring random k-colorable graphs. Combinatorics, Probability and Computing\u00a09, 45\u201377 (2000)","journal-title":"Combinatorics, Probability and Computing"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"253","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. Journal of Algorithms\u00a09, 253\u2013261 (1988)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549345_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:41:09Z","timestamp":1605624069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11549345_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}