{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:44Z","timestamp":1725795884946},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_89","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"1075-1086","source":"Crossref","is-referenced-by-count":1,"title":["Spatial Mixing of Coloring Random Graphs"],"prefix":"10.1007","author":[{"given":"Yitong","family":"Yin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"89_CR1","doi-asserted-by":"publisher","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. Annals of Mathematics\u00a0162(3), 1335\u20131351 (2005)","journal-title":"Annals of Mathematics"},{"issue":"4","key":"89_CR2","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/aama.2001.0720","volume":"26","author":"F. Chung","year":"2001","unstructured":"Chung, F., Lu, L.: The diameter of sparse random graphs. Advances in Applied Mathematics\u00a026(4), 257\u2013279 (2001)","journal-title":"Advances in Applied Mathematics"},{"key":"89_CR3","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Vilenchik, D.: Chasing the k-colorability threshold. In: FOCS, pp. 380\u2013389 (2013)","DOI":"10.1109\/FOCS.2013.48"},{"issue":"3","key":"89_CR4","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/rsa.20286","volume":"36","author":"M. Dyer","year":"2010","unstructured":"Dyer, M., Frieze, A.: Randomly coloring random graphs. Random Structures & Algorithms\u00a036(3), 251\u2013272 (2010)","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"89_CR5","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1002\/rsa.20129","volume":"29","author":"M.E. Dyer","year":"2006","unstructured":"Dyer, M.E., Flaxman, A.D., Frieze, A.M., Vigoda, E.: Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms\u00a029(4), 450\u2013465 (2006)","journal-title":"Random Struct. Algorithms"},{"key":"89_CR6","doi-asserted-by":"crossref","unstructured":"Efthymiou, C.: A simple algorithm for random colouring G (n, d\/n) using (2\u2009+\u2009\u03b5) d colours. In: SODA, pp. 272\u2013280. SIAM (2012)","DOI":"10.1137\/1.9781611973099.25"},{"key":"89_CR7","doi-asserted-by":"crossref","unstructured":"Efthymiou, C.: Mcmc sampling colourings and independent sets of G (n, d\/n) near the uniqueness threshold (2014)","DOI":"10.1137\/1.9781611973402.22"},{"key":"89_CR8","unstructured":"Efthymiou, C., Spirakis, P.G.: Randomly colouring sparse random graphs using a constant number of colours. Technical report (2007)"},{"key":"89_CR9","first-page":"53","volume":"34","author":"A. Frieze","year":"2007","unstructured":"Frieze, A., Vigoda, E.: A survey on the use of markov chains to randomly sample colourings. Oxford Lecture Series in Mathematics and its Applications\u00a034, 53 (2007)","journal-title":"Oxford Lecture Series in Mathematics and its Applications"},{"key":"89_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.jda.2010.10.002","volume":"12","author":"D. Gamarnik","year":"2012","unstructured":"Gamarnik, D., Katz, D.: Correlation decay and deterministic FPTAS for counting colorings of a graph. Journal of Discrete Algorithms\u00a012, 29\u201347 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"89_CR11","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Katz, D., Misra, S.: Strong spatial mixing for list coloring of graphs. arXiv preprint arXiv:1207.1223 (2012)","DOI":"10.1002\/rsa.20518"},{"key":"89_CR12","unstructured":"Ge, Q., Stefankovic, D.: Strong spatial mixing of q -colorings on bethe lattices. arXiv preprint arXiv:1102.2886 (2011)"},{"issue":"2","key":"89_CR13","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/S0097539704445470","volume":"35","author":"L. Goldberg","year":"2005","unstructured":"Goldberg, L., Martin, R., Paterson, M.: Strong spatial mixing with fewer colors for lattice graphs. SIAM Journal on Computing\u00a035(2), 486 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"89_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/978-3-642-40328-6_44","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P. Lu","year":"2013","unstructured":"Lu, P., Yin, Y.: Improved FPTAS for multi-spin systems. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol.\u00a08096, pp. 639\u2013654. Springer, Heidelberg (2013)"},{"key":"89_CR15","unstructured":"Mossel, E., Sly, A.: Rapid mixing of gibbs sampling on graphs that are sparse on average. In: SODA, pp. 238\u2013247 (2008)"},{"issue":"1-2","key":"89_CR16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s00440-009-0222-x","volume":"148","author":"E. Mossel","year":"2010","unstructured":"Mossel, E., Sly, A.: Gibbs rapidly samples colorings of G(n, d\/n). Probability Theory and Related Fields\u00a0148(1-2), 37\u201369 (2010)","journal-title":"Probability Theory and Related Fields"},{"key":"89_CR17","doi-asserted-by":"crossref","unstructured":"Sinclair, A., Srivastava, P., Yin, Y.: Spatial mixing and approximation algorithms for graphs with bounded connective constant. In: FOCS (2013)","DOI":"10.1109\/FOCS.2013.40"},{"key":"89_CR18","unstructured":"Weitz, D.: Mixing in time and space for discrete spin systems. PhD thesis (2004)"},{"key":"89_CR19","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: STOC, pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_89","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T15:34:52Z","timestamp":1649345692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_89"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_89","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}