{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T05:43:10Z","timestamp":1770702190071,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T00:00:00Z","timestamp":1635206400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T00:00:00Z","timestamp":1635206400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00493-021-4236-z","type":"journal-article","created":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T03:37:58Z","timestamp":1635219478000},"page":"617-658","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bounds on the Chromatic Number of Random Graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Peter","family":"Ayre","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amin","family":"Coja-Oghlan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catherine","family":"Greenhill","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,26]]},"reference":[{"key":"4236_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":"D. Achlioptas and E. Friedgut: A sharp threshold for k-colorability, Random Struct. Algorithms 14 (1999), 63\u201370.","journal-title":"Random Struct. Algorithms"},{"key":"4236_CR2","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/S0022-0000(03)00120-X","volume":"67","author":"D Achlioptas","year":"2003","unstructured":"D. Achlioptas and C. Moore: Almost all graphs with average degree 4 are 3-colorable, Journal of Computer and System Sciences 67 (2003), 441\u2013471.","journal-title":"Journal of Computer and System Sciences"},{"key":"4236_CR3","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and C. Moore: The chromatic number of random regular graphs, Proc. 8th RANDOM (2004), 219\u2013228.","DOI":"10.1007\/978-3-540-27821-4_20"},{"key":"4236_CR4","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.4007\/annals.2005.162.1335","volume":"162","author":"D Achlioptas","year":"2005","unstructured":"D. Achlioptas and A. Naor: The two possible values of the chromatic number of a random graph, Annals of Mathematics 162 (2005), 1333\u20131349.","journal-title":"Annals of Mathematics"},{"key":"4236_CR5","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF01215914","volume":"17","author":"N Alon","year":"1997","unstructured":"N. Alon and M. Krivelevich: The concentration of the chromatic number of random graphs, Combinatorica 17 (1997), 303\u2013313","journal-title":"Combinatorica"},{"key":"4236_CR6","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/s00220-015-2464-z","volume":"341","author":"V Bapst","year":"2016","unstructured":"V. Bapst, A. Coja-Oghlan, S. Hetterich, F. Rassmann and D. Vilenchik: The condensation phase transition in random graph coloring, Communications in Mathematical Physics 341 (2016), 543\u2013606.","journal-title":"Communications in Mathematical Physics"},{"key":"4236_CR7","doi-asserted-by":"publisher","first-page":"4080","DOI":"10.1214\/12-AOP816","volume":"41","author":"M Bayati","year":"2013","unstructured":"M. Bayati, D. Gamarnik and P. Tetali: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, Annals of Probability 41 (2013), 4080\u20134115.","journal-title":"Annals of Probability"},{"key":"4236_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B Bollob\u00e1s","year":"1988","unstructured":"B. Bollob\u00e1s: The chromatic number of random graphs, Combinatorica 8 (1988), 49\u201355","journal-title":"Combinatorica"},{"key":"4236_CR9","doi-asserted-by":"publisher","first-page":"P32","DOI":"10.37236\/3337","volume":"20","author":"A Coja-Oghlan","year":"2013","unstructured":"A. Coja-Oghlan: Upper-bounding the k-colorability threshold by counting covers, Electronic Journal of Combinatorics 20 (2013), P32.","journal-title":"Electronic Journal of Combinatorics"},{"key":"4236_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/j.jctb.2015.09.006","volume":"116","author":"A Coja-Oghlan","year":"2016","unstructured":"A. Coja-Oghlan, C. Efthymiou and S. Hetterich: On the chromatic number of random regular graphs, Journal of Combinatorial Theory, Series B 116 (2016), 367\u2013439.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4236_CR11","doi-asserted-by":"crossref","unstructured":"A. Coja-Oghlan, A. Erg\u00fcr, P. Gao, S. Hetterich and M. Rolvien: The rank of sparse random matrices, Proc. 31st SODA (2020), 579\u2013591.","DOI":"10.1137\/1.9781611975994.35"},{"key":"4236_CR12","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1016\/j.aim.2018.05.029","volume":"333","author":"A Coja-Oghlan","year":"2018","unstructured":"A. Coja-Oghlan, F. Krzakala, W. Perkins and L. Zdeborova: Information-theoretic thresholds from the cavity method, Advances in Mathematics 333 (2018), 694\u2013795.","journal-title":"Advances in Mathematics"},{"key":"4236_CR13","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.aim.2015.11.007","volume":"288","author":"A Coja-Oghlan","year":"2016","unstructured":"A. Coja-Oghlan and K. Panagiotou: The asymptotic k-SAT threshold, Advances in Mathematics 288 (2016), 985\u20131068.","journal-title":"Advances in Mathematics"},{"key":"4236_CR14","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1016\/j.jctb.2007.11.009","volume":"98","author":"A Coja-Oghlan","year":"2008","unstructured":"A. Coja-Oghlan, K. Panagiotou and A. Steger: On the chromatic number of random graphs, Journal of Combinatorial Theory, Series B 98 (2008), 980\u2013993.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4236_CR15","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s00220-019-03544-y","volume":"372","author":"A Coja-Oghlan","year":"2019","unstructured":"A. Coja-Oghlan and W. Perkins: Spin systems on Bethe lattices, Communications in Mathematical Physics 372 (2019), 441\u2013523.","journal-title":"Communications in Mathematical Physics"},{"key":"4236_CR16","doi-asserted-by":"publisher","first-page":"5801","DOI":"10.1093\/imrn\/rnv333","volume":"2016","author":"A Coja-Oghlan","year":"2016","unstructured":"A. Coja-Oghlan and D. Vilenchik: The chromatic number of random graphs for most average degrees, International Mathematics Research Notices 2016 (2016), 5801\u20135859.","journal-title":"International Mathematics Research Notices"},{"key":"4236_CR17","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1017\/S0963548302005254","volume":"11","author":"C Cooper","year":"2002","unstructured":"C. Cooper, A. Frieze, B. Reed and O. Riordan: Random regular graphs of non-constant degree: independence and chromatic number, Comb. Probab. Comput. 11 (2002), 323\u2013341.","journal-title":"Comb. Probab. Comput."},{"key":"4236_CR18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.20369","volume":"61","author":"J Diaz","year":"2009","unstructured":"J. Diaz, A. Kaporis, G. Kemkes, L. Kirousis, X. P\u00e9rez and N. Wormald: On the chromatic number of a random 5-regular graph, Journal of Graph Theory 61 (2009), 157\u2013191.","journal-title":"Journal of Graph Theory"},{"key":"4236_CR19","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s00220-015-2492-8","volume":"341","author":"J Ding","year":"2016","unstructured":"J. Ding, A. Sly and N. Sun: Satisfiability threshold for random regular NAE-SAT, Communications in Mathematical Physics 341 (2016), 435\u2013489.","journal-title":"Communications in Mathematical Physics"},{"key":"4236_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s11511-017-0145-9","volume":"217","author":"J Ding","year":"2016","unstructured":"J. Ding, A. Sly and N. Sun: Maximum independent sets on random regular graphs, Acta Math. 217 (2016), 263\u2013340.","journal-title":"Acta Math."},{"key":"4236_CR21","doi-asserted-by":"crossref","unstructured":"J. Ding, A. Sly and N. Sun: Proof of the satisfiability conjecture for large k, Proc. 47th STOC (2015), 59\u201368.","DOI":"10.1145\/2746539.2746619"},{"key":"4236_CR22","unstructured":"O. Dubois and J. Mandler: On the non-3-colourability of random graphs, arXiv:math\/0209087, 2002."},{"key":"4236_CR23","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi: On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl. 5 (1960), 17\u201361.","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"4236_CR24","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1023\/A:1022885828956","volume":"111","author":"S Franz","year":"2003","unstructured":"S. Franz and M. Leone: Replica bounds for optimization problems and diluted spin systems, J. Stat. Phys. 111 (2003), 535\u2013564.","journal-title":"J. Stat. Phys."},{"key":"4236_CR25","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0095-8956(92)90070-E","volume":"54","author":"A Frieze","year":"1992","unstructured":"A. Frieze and T. \u0141uczak: On the independence and chromatic numbers of random regular graphs, J. Comb. Theory B 54 (1992), 123\u2013132.","journal-title":"J. Comb. Theory B"},{"key":"4236_CR26","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak and A. Ruci\u0144ski: Random Graphs, Wiley, 2000.","DOI":"10.1002\/9781118032718"},{"key":"4236_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00220-002-0773-5","volume":"233","author":"F Guerra","year":"2003","unstructured":"F. Guerra: Broken replica symmetry bounds in the mean field spin glass model, Comm. Math. Phys., 233 (2003), 1\u201312.","journal-title":"Comm. Math. Phys."},{"key":"4236_CR28","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.aim.2009.08.006","volume":"223","author":"G Kemkes","year":"2010","unstructured":"G. Kemkes, X. P\u00e9rez-Gim\u00e9nez and N. Wormald: On the chromatic number of random d-regular graphs, Advances in Mathematics 223 (2010), 300\u2013328.","journal-title":"Advances in Mathematics"},{"key":"4236_CR29","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1002\/rsa.1013","volume":"18","author":"M Krivelevich","year":"2001","unstructured":"M. Krivelevich, B. Sudakov, V. Vu and N. Wormald: Random regular graphs of high degree, Random Struct. Algor. 18 (2001), 346\u2013363.","journal-title":"Random Struct. Algor."},{"key":"4236_CR30","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1007\/s10955-018-1964-6","volume":"173","author":"M Lelarge","year":"2018","unstructured":"M. Lelarge and M. Oulamara: Replica bounds by combinatorial interpolation for diluted spin systems, J. Stat. Phys 173 (2018), 917\u2013940.","journal-title":"J. Stat. Phys"},{"key":"4236_CR31","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T \u0141uczak","year":"1991","unstructured":"T. \u0141uczak: The chromatic number of random graphs, Combinatorica 11 (1991), 45\u201354","journal-title":"Combinatorica"},{"key":"4236_CR32","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579304","volume":"7","author":"D Matula","year":"1987","unstructured":"D. Matula: Expose-and-merge exploration and the chromatic number of a random graph, Combinatorica 7 (1987), 275\u2013284.","journal-title":"Combinatorica"},{"key":"4236_CR33","first-page":"175","volume":"87","author":"D Matula","year":"1987","unstructured":"D. Matula and L. Ku\u010dera: An expose-and-merge algorithm and the chromatic number of a random graph. Proc. Random Graphs 87 (1987), 175\u2013187.","journal-title":"Proc. Random Graphs"},{"key":"4236_CR34","doi-asserted-by":"crossref","unstructured":"M. M\u00e9zard and A. Montanari: Information, Physics and Computation, Oxford University Press, 2009.","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"4236_CR35","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/PL00011099","volume":"20","author":"M M\u00e9zard","year":"2001","unstructured":"M. M\u00e9zard and G. Parisi: The Bethe lattice spin glass revisited, European Physical Journal B 20 (2001), 217\u2013233.","journal-title":"European Physical Journal B"},{"key":"4236_CR36","doi-asserted-by":"crossref","unstructured":"D. Panchenko: The Sherrington-Kirkpatrick model, Springer, 2013.","DOI":"10.1007\/978-1-4614-6289-7"},{"key":"4236_CR37","doi-asserted-by":"publisher","first-page":"1315","DOI":"10.1214\/11-AOP696","volume":"41","author":"D Panchenko","year":"2013","unstructured":"D. Panchenko: Spin glass models from the point of view of spin distributions, Annals of Probability 41 (2013), 1315\u20131361.","journal-title":"Annals of Probability"},{"key":"4236_CR38","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00440-004-0342-2","volume":"130","author":"D Panchenko","year":"2004","unstructured":"D. Panchenko and M. Talagrand: Bounds for diluted mean-fields spin glass models, Probab. Theory Relat. Fields 130 (2004), 319\u2013336.","journal-title":"Probab. Theory Relat. Fields"},{"key":"4236_CR39","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02579208","volume":"7","author":"E Shamir","year":"1987","unstructured":"E. Shamir and J. Spencer: Sharp concentration of the chromatic number of random graphs Gn,p, Combinatorica 7 (1987), 121\u2013129.","journal-title":"Combinatorica"},{"key":"4236_CR40","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1017\/S0963548306007693","volume":"16","author":"L Shi","year":"2007","unstructured":"L. Shi and N. Wormald: Colouring random 4-regular graphs, Combinatorics, Probability and Computing 16 (2007), 309\u2013344.","journal-title":"Combinatorics, Probability and Computing"},{"key":"4236_CR41","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1017\/S0963548306007954","volume":"16","author":"L Shi","year":"2007","unstructured":"L. Shi and N. Wormald: Colouring random regular graphs, Combinatorics, Probability and Computing 16 (2007), 459\u2013494.","journal-title":"Combinatorics, Probability and Computing"},{"key":"4236_CR42","doi-asserted-by":"crossref","unstructured":"A. Sly, N. Sun and Y. Zhang: The number of solutions for random regular NAE-SAT, Proc. 57th FOCS (2016), 724\u2013731; full version available as arXiv:1604.08546.","DOI":"10.1109\/FOCS.2016.82"},{"key":"4236_CR43","unstructured":"M. Talagrand: Spin glasses: a challenge for mathematicians, Springer, 2003."},{"key":"4236_CR44","doi-asserted-by":"publisher","first-page":"031131","DOI":"10.1103\/PhysRevE.76.031131","volume":"76","author":"L Zdeborov\u00e1","year":"2007","unstructured":"L. Zdeborov\u00e1 and F. Krzakala: Phase transitions in the coloring of random graphs, Phys. Rev. E 76 (2007), 031131.","journal-title":"Phys. Rev. E"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4236-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-021-4236-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4236-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T13:04:51Z","timestamp":1670677491000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-021-4236-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,26]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["4236"],"URL":"https:\/\/doi.org\/10.1007\/s00493-021-4236-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,26]]},"assertion":[{"value":"30 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}