{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:53:54Z","timestamp":1725490434567},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_67","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"777-788","source":"Crossref","is-referenced-by-count":1,"title":["On the Chromatic Number of Random Graphs"],"prefix":"10.1007","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"67_CR1","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. System Sci.\u00a057(2), 187\u2013199 (1998)","journal-title":"J. Comput. System Sci."},{"key":"67_CR2","doi-asserted-by":"crossref","unstructured":"Zeitlhofer, T., Wess, B.: A comparison of graph coloring heuristics for register allocation based on coalescing in interval graphs. In: ISCAS (4), 529\u2013532 (2004)","DOI":"10.1109\/ISCAS.2004.1329057"},{"issue":"3","key":"67_CR3","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.39.3.378","volume":"39","author":"D.S. Johnson","year":"1991","unstructured":"Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Oper. Res.\u00a039(3), 378\u2013406 (1991)","journal-title":"Oper. Res."},{"key":"67_CR4","doi-asserted-by":"crossref","unstructured":"Krivelevich, M.: Coloring random graphs\u2014an algorithmic perspective. In: Mathematics and computer science, II (Versailles, 2002). Trends Math. Birkh\u00e4user, Basel, pp. 175\u2013195 (2002)","DOI":"10.1007\/978-3-0348-8211-8_11"},{"issue":"2","key":"67_CR5","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/S0022-0000(03)00120-X","volume":"67","author":"D. Achlioptas","year":"2003","unstructured":"Achlioptas, D., Moore, C.: Almost all graphs with average degree 4 are 3-colorable. J. Comput. System Sci.\u00a067(2), 441\u2013471 (2003), Special issue on STOC 2002 (Montreal, QC)","journal-title":"J. Comput. System Sci."},{"key":"67_CR6","doi-asserted-by":"crossref","unstructured":"Jia, H., Moore, C.: How much backtracking does it take to color random graphs? Rigorous results on heavy tails (2004)","DOI":"10.1007\/978-3-540-30201-8_58"},{"key":"67_CR7","doi-asserted-by":"publisher","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","volume":"89","author":"R. Mulet","year":"2002","unstructured":"Mulet, R., Pagnani, A., Weigt, M., Zecchina, R.: Coloring random graphs. Physical Review Letters\u00a089, 268701 (2002)","journal-title":"Physical Review Letters"},{"key":"67_CR8","doi-asserted-by":"publisher","first-page":"36702","DOI":"10.1103\/PhysRevE.68.036702","volume":"68","author":"A. Braunstein","year":"2003","unstructured":"Braunstein, A., Mulet, R., Pagnani, A., Weigt, M., Zecchina, R.: Polynomial iterative algorithms for coloring and analyzing random graphs. Physical Review E\u00a068, 36702 (2003)","journal-title":"Physical Review E"},{"issue":"3","key":"67_CR9","doi-asserted-by":"crossref","first-page":"1335","DOI":"10.4007\/annals.2005.162.1335","volume":"162","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas, D., Naor, A.: The two possible values of the chromatic number of a random graph. Ann. of Math. (2)\u00a0162(3), 1335\u20131351 (2005)","journal-title":"Ann. of Math. (2)"},{"key":"67_CR10","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs. I. Publ. Math. Debrecen\u00a06, 290\u2013297 (1959)","journal-title":"I. Publ. Math. Debrecen"},{"issue":"1","key":"67_CR11","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. Combinatorica\u00a08(1), 49\u201355 (1988)","journal-title":"Combinatorica"},{"issue":"3","key":"67_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01205080","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(3), 295\u2013297 (1991)","journal-title":"Combinatorica"},{"issue":"1","key":"67_CR13","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 on random graphs G n,p. Combinatorica\u00a07(1), 121\u2013129 (1987)","journal-title":"Combinatorica"},{"issue":"3","key":"67_CR14","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF01215914","volume":"17","author":"N. Alon","year":"1997","unstructured":"Alon, N., Krivelevich, M.: The concentration of the chromatic number of random graphs. Combinatorica\u00a017(3), 303\u2013313 (1997)","journal-title":"Combinatorica"},{"issue":"1","key":"67_CR15","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 Structures Algorithms\u00a014(1), 63\u201370 (1999)","journal-title":"Random Structures Algorithms"},{"key":"67_CR16","unstructured":"http:\/\/www.ti.inf.ethz.ch\/as\/people\/panagiotou\/papers\/CNoSRG.ps"},{"key":"67_CR17","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The probabilistic method, 2nd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], Chichester (2000)","edition":"2"},{"key":"67_CR18","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Rucinski, A.: Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, Chichester (2000)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T22:39:26Z","timestamp":1684017566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}