{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T06:44:25Z","timestamp":1745649865312},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00493-016-3394-x","type":"journal-article","created":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T04:14:44Z","timestamp":1497327284000},"page":"341-380","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Local Convergence of Random Graph Colorings"],"prefix":"10.1007","volume":"38","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charilaos","family":"Efthymiou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nor","family":"Jaafari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"3394_CR1","first-page":"63","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":"Algorithms"},{"key":"3394_CR2","first-page":"793","volume-title":"Proc. 49th FOCS","author":"D. Achlioptas","year":"2008","unstructured":"D. Achlioptas and A. Coja-Oghlan: Algorithmic barriers from phase transitions, Proc. 49th FOCS (2008), 793\u2013802."},{"key":"3394_CR3","first-page":"204","volume-title":"Proc. 38th FOCS","author":"D. Achlioptas","year":"1997","unstructured":"D. Achlioptas and M. Molloy: The analysis of a list-coloring algorithm on a random graph, Proc. 38th FOCS (1997), 204\u2013212."},{"key":"3394_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":"3394_CR5","volume-title":"Probability on discrete structures","author":"D. Aldous","year":"2004","unstructured":"D. Aldous and J. Steele: The objective method: probabilistic combinatorial optimization and local weak convergence (2003), in: Probability on discrete structures (H. Kesten (ed.)), Springer 2004."},{"key":"3394_CR6","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":"3394_CR7","unstructured":"V. Bapst, A. Coja-Oghlan and C. Efthymiou: Planting colourings silently, arXiv:1411.0610 (2014)."},{"key":"3394_CR8","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 Dan Vilenchik: The condensation phase transition in random graph coloring, Communications in Mathematical Physics 341 (2016), 543\u2013606.","journal-title":"Communications in Mathematical Physics"},{"key":"3394_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/EJP.v6-96","volume":"6","author":"I. Benjamini","year":"2001","unstructured":"I. Benjamini and O. Schramm: Recurrence of distributional limits of nite planar graphs, Electronic J. Probab. 6 (2001), 1\u201313.","journal-title":"Electronic J. Probab."},{"key":"3394_CR10","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/090755783","volume":"25","author":"N. Bhatnagar","year":"2011","unstructured":"N. Bhatnagar, J. Vera, E. Vigoda and D. Weitz: Reconstruction for Colorings on Trees, SIAM Journal on Discrete Mathematics. 25 (2011), 809\u2013826.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"3394_CR11","doi-asserted-by":"crossref","unstructured":"N. Bhatnagar, A. Sly and P. Tetali: Decay of correlations for the hardcore model on the d-regular random graph, Electronic Journal of Probability 21 (2016).","DOI":"10.1214\/16-EJP3552"},{"key":"3394_CR12","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":"3394_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00440-014-0590-8","volume":"163","author":"C. Bordenave","year":"2015","unstructured":"C. Bordenave and P. Caputo: Large deviations of empirical neighborhood distri- bution in sparse random graphs, Probability Theory and Related Fields 163 (2015), 149\u2013222.","journal-title":"Probability Theory and Related Fields"},{"key":"3394_CR14","doi-asserted-by":"crossref","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":"3394_CR15","volume-title":"International Mathematics Research Notices","author":"A. Coja-Oghlan","year":"2015","unstructured":"A. Coja-Oghlan and D. Vilenchik: The chromatic number of random graphs for most average degrees, International Mathematics Research Notices, (2015): rnv333."},{"key":"3394_CR16","first-page":"251","volume":"36","author":"M. E. Dyer","year":"2010","unstructured":"M. E. Dyer and A. M. Frieze: Randomly coloring random graphs, Random Struct. Algorithms 36 (2010), 251\u2013272.","journal-title":"Algorithms"},{"key":"3394_CR17","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1002\/rsa.20129","volume":"29","author":"M. Dyer","year":"2006","unstructured":"M. Dyer, A. Flaxman, A. Frieze and E. Vigoda: Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures and Algorithms 29 (2006), 450\u2013465.","journal-title":"Random Structures and Algorithms"},{"key":"3394_CR18","first-page":"305","volume-title":"Proc. 25th SODA","author":"C. Efthymiou","year":"2014","unstructured":"C. Efthymiou: MCMC sampling colourings and independent sets of G(n;d=n) near uniqueness threshold, Proc. 25th SODA (2014), 305\u2013316."},{"key":"3394_CR19","first-page":"371","volume-title":"Proc. 22nd ESA","author":"C. Efthymiou","year":"2014","unstructured":"C. Efthymiou: Switching colouring of G(n;d=n) for sampling up to Gibbs unique- ness threshold, Proc. 22nd ESA (2014), 371\u2013381."},{"key":"3394_CR20","first-page":"756","volume-title":"Proc. 19th RANDOM","author":"C. Efthymiou","year":"2015","unstructured":"C. Efthymiou: Reconstruction\/non-reconstruction thresholds for colourings of gen- eral Galton-Watson trees, Proc. 19th RANDOM (2015), 756\u2013774."},{"key":"3394_CR21","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u0151s","year":"1959","unstructured":"P. Erd\u0151s: Graph theory and probability, Canad. J. Math. 11 (1959), 34\u201338.","journal-title":"Canad. J. Math."},{"key":"3394_CR22","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, Magayar Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960), 17\u201361.","journal-title":"Magayar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"3394_CR23","first-page":"194","volume-title":"Proc. 48th FOCS","author":"A. Gerschenfeld","year":"2007","unstructured":"A. Gerschenfeld and A. Montanari: Reconstruction for models on random graphs, Proc. 48th FOCS (2007), 194\u2013204."},{"key":"3394_CR24","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. Grimmett","year":"1975","unstructured":"G. Grimmett and C. McDiarmid: On colouring random graphs, Mathematical Proceedings of the Cambridge Philosophical Society 77 (1975), 313\u2013324.","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"3394_CR25","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1088\/0305-4470\/31\/2\/009","volume":"31","author":"D. A. Johnston","year":"1998","unstructured":"D. A. Johnston and P. Plech\u00e1\u010d: Equivalence of ferromagnetic spin models on trees and random graphs, J. Phys. A 31 (1998), 475\u2013482.","journal-title":"J. Phys. A"},{"key":"3394_CR26","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0020-0190(98)00092-1","volume":"67","author":"M. Krivelevich","year":"1998","unstructured":"M. Krivelevich and B. Sudakov: Coloring random graphs, Information Processing Letters 67 (1998), 71\u201374.","journal-title":"Information Processing Letters"},{"key":"3394_CR27","doi-asserted-by":"publisher","first-page":"10318","DOI":"10.1073\/pnas.0703685104","volume":"104","author":"F. Krzakala","year":"2007","unstructured":"F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zde- borova: Gibbs states and the set of solutions of random constraint satisfaction prob- lems, Proc. National Academy of Sciences 104 (2007), 10318\u201310323.","journal-title":"Proc. National Academy of Sciences"},{"key":"3394_CR28","doi-asserted-by":"crossref","unstructured":"F. Krzakala, A. Pagnani and M. Weigt: Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs, Phys. Rev. E 70 (2004), 046705.","DOI":"10.1103\/PhysRevE.70.046705"},{"key":"3394_CR29","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T. Luczak","year":"1991","unstructured":"T. Luczak: The chromatic number of random graphs, Combinatorica 11 (1991), 45\u201354.","journal-title":"Combinatorica"},{"key":"3394_CR30","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01205080","volume":"11","author":"T. Luczak","year":"1991","unstructured":"T. Luczak: A note on the sharp concentration of the chromatic number of random graphs, Combinatorica 11 (1991), 295\u2013297.","journal-title":"Combinatorica"},{"key":"3394_CR31","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":"3394_CR32","volume-title":"Oxford University Press","author":"M. M\u00e9zard","year":"2009","unstructured":"M. M\u00e9zard and A. Montanari: Information, physics and computation, Oxford University Press 2009."},{"key":"3394_CR33","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, Eur. Phys. J. B 20 (2001), 217\u2013233.","journal-title":"Eur. Phys. J. B"},{"key":"3394_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1022221005097","volume":"111","author":"M. M\u00e9zard","year":"2003","unstructured":"M. M\u00e9zard and G. Parisi: The cavity method at zero temperature, Journal of Statistical Physics 111 (2003), 1\u201334.","journal-title":"Journal of Statistical Physics"},{"key":"3394_CR35","doi-asserted-by":"crossref","unstructured":"M. M\u00e9zard, M. Palassini and O. Rivoire: Landscape of solutions in constraint satisfaction problems, Phys. Rev. E 95 (2005), 200202.","DOI":"10.1103\/PhysRevLett.95.200202"},{"key":"3394_CR36","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M. M\u00e9zard","year":"2002","unstructured":"M. M\u00e9zard, G. Parisi and R. Zecchina: Analytic and algorithmic solution of random satisfiability problems, Science 297 (2002), 812\u2013815.","journal-title":"Science"},{"key":"3394_CR37","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/2213977.2214060","volume-title":"Proc. 43rd STOC","author":"M. Molloy","year":"2012","unstructured":"M. Molloy: The freezing threshold for k-colourings of a random graph, Proc. 43rd STOC (2012), 921\u2013930."},{"key":"3394_CR38","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00440-010-0315-6","volume":"152","author":"A. Montanari","year":"2012","unstructured":"A. Montanari, E. Mossel and A. Sly: The weak limit of Ising models on locally tree-like graphs, Probab. Theory Relat. Fields 152 (2012), 31\u201351.","journal-title":"Probab. Theory Relat. Fields"},{"key":"3394_CR39","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1137\/090755862","volume":"25","author":"A. Montanari","year":"2011","unstructured":"A. Montanari, R. Restrepo and P. Tetali: Reconstruction and clustering in random constraint satisfaction problems, SIAM J. Discrete Math. 25 (2011), 771\u2013808.","journal-title":"SIAM J. Discrete Math."},{"key":"3394_CR40","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00440-009-0222-x","volume":"148","author":"E. Mossel","year":"2010","unstructured":"E. Mossel and A. Sly: Gibbs rapidly samples colorings of G(n;d=n), Probability Theory and Related Fields 148 (2010), 37\u201369.","journal-title":"Probability Theory and Related Fields"},{"key":"3394_CR41","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 G(n;p), Combinatorica 7 (1987), 121\u2013129.","journal-title":"Combinatorica"},{"key":"3394_CR42","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/s00220-009-0783-7","volume":"288","author":"A. Sly","year":"2009","unstructured":"A. Sly: Reconstruction of random colourings, Comm. Math. Phys. 288 (2009), 943\u2013961.","journal-title":"Comm. Math. Phys."},{"key":"3394_CR43","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0963548315000103","volume":"25","author":"L. Warnke","year":"2016","unstructured":"L. Warnke: On the method of typical bounded differences, Combinatorics, Proba- bility and Computing, 25 (2016) 269\u2013299.","journal-title":"Proba- bility and Computing"},{"key":"3394_CR44","doi-asserted-by":"crossref","unstructured":"L. Zdeborov\u00e1 and F. Krzakala: Phase transitions in the coloring of random graphs, Phys. Rev. E 76 (2007), 031131.","DOI":"10.1103\/PhysRevE.76.031131"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-016-3394-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3394-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3394-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,10]],"date-time":"2020-10-10T02:39:54Z","timestamp":1602297594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-016-3394-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["3394"],"URL":"https:\/\/doi.org\/10.1007\/s00493-016-3394-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,13]]}}}