{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T06:52:41Z","timestamp":1765608761568},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T00:00:00Z","timestamp":1603065600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>G<\/jats:italic> be a graph on <jats:italic>n<\/jats:italic> vertices and with maximum degree \u0394, and let <jats:italic>k<\/jats:italic> be an integer. The <jats:italic>k-recolouring graph of G<\/jats:italic> is the graph whose vertices are <jats:italic>k<\/jats:italic>-colourings of <jats:italic>G<\/jats:italic> and where two <jats:italic>k<\/jats:italic>-colourings are adjacent if they differ at exactly one vertex. It is well known that the <jats:italic>k<\/jats:italic>-recolouring graph is connected for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000139_inline1.png\" \/><jats:tex-math>\n$k\\geq \\Delta+2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Feghali, Johnson and Paulusma (<jats:italic>J. Graph Theory<\/jats:italic><jats:bold>83<\/jats:bold> (2016) 340\u2013358) showed that the (\u0394 + 1)-recolouring graph is composed by a unique connected component of size at least 2 and (possibly many) isolated vertices.<\/jats:p><jats:p>In this paper, we study the proportion of isolated vertices (also called <jats:italic>frozen<\/jats:italic> colourings) in the (\u0394 + 1)-recolouring graph. Our first contribution is to show that if <jats:italic>G<\/jats:italic> is connected, the proportion of frozen colourings of <jats:italic>G<\/jats:italic> is exponentially smaller in <jats:italic>n<\/jats:italic> than the total number of colourings. This motivates the use of the Glauber dynamics to approximate the number of (\u0394 + 1)-colourings of a graph. In contrast to the conjectured mixing time of <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log <jats:italic>n<\/jats:italic>) for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000139_inline1.png\" \/><jats:tex-math>\n$k\\geq \\Delta+2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> colours, we show that the mixing time of the Glauber dynamics for (\u0394 + 1)-colourings restricted to non-frozen colourings can be \u03a9(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>). Finally, we prove some results about the existence of graphs with large girth and frozen colourings, and study frozen colourings in random regular graphs.<\/jats:p>","DOI":"10.1017\/s0963548320000139","type":"journal-article","created":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T08:39:27Z","timestamp":1603096767000},"page":"330-343","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Frozen (\u0394 + 1)-colourings of bounded degree graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[]},{"given":"Guillem","family":"Perarnau","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,10,19]]},"reference":[{"key":"S0963548320000139_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"S0963548320000139_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.117"},{"key":"S0963548320000139_ref5","volume-title":"Graph Theory","author":"Diestel","year":"2005"},{"key":"S0963548320000139_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000683"},{"key":"S0963548320000139_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2016.06.008"},{"key":"S0963548320000139_ref9","first-page":"20","article-title":"Asymptotic eigenvalue distribution of random lifts","volume":"2","author":"Fortin","year":"2013","journal-title":"Waterloo Math. Review"},{"key":"S0963548320000139_ref7","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1002\/jgt.22000","article-title":"A reconfigurations analogue of Brooks\u2019 theorem and its consequences","volume":"83","author":"Feghali","year":"2016","journal-title":"J. Graph Theory"},{"key":"S0963548320000139_ref12","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","article-title":"On the complexity of reconfiguration problems","volume":"412","author":"Ito","year":"2011","journal-title":"Theoret. Comput. Sci."},{"key":"S0963548320000139_ref2","unstructured":"[2] Bonamy, M. and Bousquet, N. (2014) Reconfiguring independent sets in cographs. CoRR."},{"key":"S0963548320000139_ref1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0012-365X(74)90118-6","article-title":"The asymptotic number of non-negative integer matrices with given row and column sums","volume":"10","author":"Bender","year":"1974","journal-title":"Discrete Math."},{"key":"S0963548320000139_ref22","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"},{"key":"S0963548320000139_ref19","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF02199113","article-title":"Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem","volume":"86","author":"Salas","year":"1997","journal-title":"J. Statist. Phys."},{"key":"S0963548320000139_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"S0963548320000139_ref21","volume-title":"Series","author":"van den Heuvel","year":"2013"},{"key":"S0963548320000139_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48115-7_2"},{"key":"S0963548320000139_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"S0963548320000139_ref20","doi-asserted-by":"crossref","first-page":"1182","DOI":"10.1007\/s10878-015-9947-x","article-title":"Reconfiguration of dominating sets","volume":"32","author":"Suzuki","year":"2016","journal-title":"J. Comb. Optim."},{"key":"S0963548320000139_ref11","unstructured":"[11] Hayes, T. P. and Sinclair, A. (2005) A general lower bound for mixing of single-site dynamics on graphs. In 46th Annual IEEE Symposium on Foundations of Computer Science 2005 (FOCS 2005), pp. 511\u2013520, IEEE."},{"key":"S0963548320000139_ref13","unstructured":"[13] Ito., T., Kaminski, M. and Ono, H. (2014) Independent set reconfiguration in graphs without large bicliques. In ISAAC\u201914."},{"key":"S0963548320000139_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.134"},{"key":"S0963548320000139_ref3","first-page":"110","volume-title":"Computer Science","author":"Bonsma","year":"2014"},{"key":"S0963548320000139_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/07070440X"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000139","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T12:01:30Z","timestamp":1618315290000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000139\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,19]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["S0963548320000139"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000139","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}