{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:57:40Z","timestamp":1760241460535,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,3,29]],"date-time":"2018-03-29T00:00:00Z","timestamp":1522281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["281291"],"award-info":[{"award-number":["281291"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A k-colouring of a graph G with colours    1 , 2 , \u2026 , k    is canonical with respect to an ordering    \u03c0 =  v 1  ,  v 2  , \u2026 ,  v n     of the vertices of G if adjacent vertices are assigned different colours and, for    1 \u2264 c \u2264 k    , whenever colour c is assigned to a vertex    v i    , each colour less than c has been assigned to a vertex that precedes    v i    in   \u03c0   . The canonical k-colouring graph of G with respect to \u03c0 is the graph     Can k \u03c0   ( G )     with vertex set equal to the set of canonical k-colourings of G with respect to   \u03c0   , with two of these being adjacent if and only if they differ in the colour assigned to exactly one vertex. Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs is studied. It is shown that for complete multipartite graphs, and bipartite graphs there exists a vertex ordering   \u03c0   such that     Can k \u03c0   ( G )     is connected for large enough values of k. It is proved that a canonical colouring graph of a complete multipartite graph usually does not have a Hamilton cycle, and that there exists a vertex ordering   \u03c0   such that     Can k \u03c0   (  K  m , n   )     has a Hamilton path for all    k \u2265 3    . The paper concludes with a detailed consideration of     Can k \u03c0   (  K  2 , 2 , \u2026 , 2   )     . For each    k \u2265 \u03c7    and all vertex orderings   \u03c0   , it is proved that     Can k \u03c0   (  K  2 , 2 , \u2026 , 2   )     is either disconnected or isomorphic to a particular tree.<\/jats:p>","DOI":"10.3390\/a11040040","type":"journal-article","created":{"date-parts":[[2018,3,29]],"date-time":"2018-03-29T12:51:56Z","timestamp":1522327916000},"page":"40","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Connectivity and Hamiltonicity of Canonical Colouring Graphs of Bipartite and Complete Multipartite Graphs"],"prefix":"10.3390","volume":"11","author":[{"given":"Ruth","family":"Haas","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Hawaii at Manoa, Honolulu, HI 96822, USA"},{"name":"Smith College, Northampton, MA 01063, USA"}]},{"given":"Gary","family":"MacGillivray","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Victoria, Victoria, BC V8W 2Y2, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2018,3,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.26493\/1855-3974.168.464","article-title":"The canonical colouring graph of trees and cycles","volume":"5","author":"Haas","year":"2012","journal-title":"Ars Math. Contemp."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(76)90014-4","article-title":"A Gray code for set partitions","volume":"5","author":"Kaye","year":"1976","journal-title":"Inf. Process. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (2008). Graph Theory, Springer. GTM 224.","DOI":"10.1007\/978-1-84628-970-5"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Blackburn, S.R., Gerke, S., and Wildon, M. (2013). The complexity of change, Surveys in Combinatorics 2013. London Mathematical Society Lecture Notes Series 409, Cambridge University Press.","DOI":"10.1017\/CBO9781139506748"},{"key":"ref_5","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":"Theor. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1002\/rsa.20129","article-title":"Randomly colouring sparse random graphs with fewer colours than the maximum degree","volume":"29","author":"Dyer","year":"2006","journal-title":"Random Struct. Algorithms"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1002\/rsa.3240070205","article-title":"A very simple algorithm for estimating the number of k-colourings of a low-degree graph","volume":"7","author":"Jerrum","year":"1995","journal-title":"Random Struct. Algorithms"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1137\/090779516","article-title":"The Glauber dynamics for colourings of bounded degree trees","volume":"25","author":"Lucier","year":"2011","journal-title":"SIAM J. Discret. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1016\/j.disc.2007.07.028","article-title":"Connectedness of the graph of vertex colourings","volume":"308","author":"Cereceda","year":"2008","journal-title":"Discret. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","article-title":"Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances","volume":"410","author":"Bonsma","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/jgt.20514","article-title":"Finding Paths Between 3-colourings","volume":"67","author":"Cereceda","year":"2011","journal-title":"J. Graph Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.26493\/1855-3974.196.0df","article-title":"Gray code numbers for graphs","volume":"4","author":"Choo","year":"2011","journal-title":"Ars Math. Contemp."},{"key":"ref_13","unstructured":"Cavers, M., and Seyffarth, K. (2015). Gray code numbers of 2-trees, Unpublished work."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"647","DOI":"10.5666\/KMJ.2016.56.3.647","article-title":"Reconfiguring k-colorings of complete bipartite graphs","volume":"56","author":"Celaya","year":"2016","journal-title":"Kyungpook Math. J."},{"key":"ref_15","unstructured":"Bard, S. (2014). Colour Graphs of Complete Multipartite Graphs. [Master\u2019s Thesis, University of Victoria]. Available online: https:\/\/dspace.library.uvic.ca:8443\/handle\/1828\/5815."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1016\/j.ejc.2009.03.011","article-title":"Mixing 3-colourings in bipartite graphs","volume":"30","author":"Cereceda","year":"2009","journal-title":"Eur. J. Comb."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.tcs.2014.04.011","article-title":"Reconfiguration of list L(2, 1)-labelings in a graph","volume":"544","author":"Ito","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","unstructured":"Finbow, S., and MacGillivray, G. (2016). Hamiltonicity of Bell and Stirling Colour Graphs, Unpublished work."},{"key":"ref_19","first-page":"85","article-title":"Gray codes for set partitions and restricted growth tails","volume":"10","author":"Ruskey","year":"1994","journal-title":"Australas. J. Comb."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:58:56Z","timestamp":1760194736000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,29]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["a11040040"],"URL":"https:\/\/doi.org\/10.3390\/a11040040","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,3,29]]}}}