{"entities":{"Q2331438":{"pageid":2342181,"ns":120,"title":"Item:Q2331438","lastrevid":56665347,"modified":"2026-03-18T13:35:58Z","type":"item","id":"Q2331438","labels":{"en":{"language":"en","value":"Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7123884"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$4D442CCA-E126-4E77-B147-D7A997202DB6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ee6ab6d8ede783ed4a7c03af80cc7a9ace044ad","datavalue":{"value":{"text":"Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2331438$E49F534C-FDBF-4F7B-B277-BEA12DFD66E6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b46f5b6619857b6258940ceadec04137325bfed","datavalue":{"value":"1461.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$21E367C0-F87A-4BD9-8851-26FEC381DB9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a81e1fc606ceccab0b854c7f93b60b54031f4fc","datavalue":{"value":{"entity-type":"item","numeric-id":284743,"id":"Q284743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$8933E0C3-2535-4E8A-BE20-C8B0245DBA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"57555e49e581043524b19e8ff224491cb25ceec4","datavalue":{"value":{"entity-type":"item","numeric-id":189757,"id":"Q189757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$99A03BE1-BA03-4C0D-A464-6D18D74FF2F2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$BD966F60-37AA-463F-92A2-9AF969D5824C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"362960159b173a98e6b7060e1eb441bfdc739e81","datavalue":{"value":{"time":"+2019-10-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2331438$60905227-A357-42CA-B536-0B15133BF101","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b4cb43b6055bc4c68eaadb1d7e4a71b0d73584f2","datavalue":{"value":"Summary: A \\(k\\)-colouring of a graph \\(G\\) with colours \\(1, 2, \\dots, k\\) is \\textit{canonical} with respect to an ordering \\(\\pi = v_1, v_2, \\dots, v_n\\) of the vertices of \\(G\\) if adjacent vertices are assigned different colours and, for \\(1 \\leq c \\leq 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 \\(\\pi\\). The \\textit{canonical \\(k\\)-colouring graph of \\(G\\) with respect to \\(\\pi\\)} is the graph \\(\\operatorname{Can}_k^\\pi(G)\\) with vertex set equal to the set of canonical \\(k\\)-colourings of \\(G\\) with respect to \\(\\pi\\), 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 \\(\\pi\\) such that \\(\\operatorname{Can}_k^\\pi(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 \\(\\pi\\) such that \\(\\operatorname{Can}_k^\\pi(K_{m, n})\\) has a Hamilton path for all \\(k \\geq 3\\). The paper concludes with a detailed consideration of \\(\\operatorname{Can}_k^\\pi(K_{2, 2, \\ldots, 2})\\). For each \\(k \\geq \\chi\\) and all vertex orderings \\(\\pi\\), it is proved that \\(\\operatorname{Can}_k^\\pi(K_{2, 2, \\dots, 2})\\) is either disconnected or isomorphic to a particular tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331438$CCDA312C-14F2-49A3-BF11-C76413999F2F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$C0F42BA7-C192-4543-84A9-16CA321CFE72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$695C20ED-3080-40D1-B7FF-7D4D97A3BBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$4459BE0D-F5C1-4BF7-8B11-4097087A452C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$66486B0D-32B6-4011-AB75-1F3FAAB95750","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"598ba3b29003ae7a794e2f6b5f320c9b5dcbe45e","datavalue":{"value":"7123884","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$B5D39396-C502-41F2-B119-14DCF35BC753","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87069cbf33644658b2a664bd0d8644f30620f9e8","datavalue":{"value":"reconfiguration problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331438$B9540C8A-F6AC-4865-BC1F-3C07ABB555EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"def48283d510794913c58f78056b808e00633a5c","datavalue":{"value":"graph colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331438$3405271E-F1FE-44D3-A890-CC0577E10715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51a5f2b554ad725199c724ddbac3b61a9fd8af1","datavalue":{"value":"Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331438$CFCA3008-0EBF-48AF-A018-54A878F35985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae9d25fd7dc2391d9ae1f090e7c9078db3e76d93","datavalue":{"value":"Gray codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331438$7C4F50CF-FC83-49E5-9788-C2D70CEB25FD","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$A3473750-F6EF-43FD-92EA-88D0EEB2C03C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5029e44b60be4847ee629be886f04020180e739","datavalue":{"value":"https://doi.org/10.3390/a11040040","type":"string"},"datatype":"url"},"type":"statement","id":"Q2331438$D4D9981B-792E-42A5-A561-50F21BE74600","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a5daa13cb56296b3d81ab7a3230523ba8a8c6a85","datavalue":{"value":"W2794856912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$96BC6A09-5D3F-4F07-A8D3-1DF8D192EB29","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4da7e7f287511c82ecf40c40ba7f34cc54ede94","datavalue":{"value":{"entity-type":"item","numeric-id":2892015,"id":"Q2892015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$8A183C25-6CA9-478D-B8BB-262E8A7C0EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2908d2f36f1b71e6478519e8616e1be063a6aac7","datavalue":{"value":{"entity-type":"item","numeric-id":1239129,"id":"Q1239129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$23C5882D-F3D1-4547-B8DD-97D1EA34CE99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$365BF95E-4778-4D61-8C1C-031F16EA12BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f80e72c60e965ff74053ca242a8f8bc9d31aec4","datavalue":{"value":{"entity-type":"item","numeric-id":2875857,"id":"Q2875857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$70B952E0-59BD-44C7-8BA3-28751CAF61D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5adb753426206a01b9fcf78479e586e248e7d827","datavalue":{"value":{"entity-type":"item","numeric-id":631762,"id":"Q631762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$96FA8226-3B9D-4026-8DC1-F7F5ACB06807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aaf62d8b0dd458e9bc5f818a51a609edac9992f","datavalue":{"value":{"entity-type":"item","numeric-id":3419603,"id":"Q3419603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$635EFED5-E1F5-4FBB-B80F-DE123345544D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f510dc95435ae5bc886b3a1646fe55f24094a286","datavalue":{"value":{"entity-type":"item","numeric-id":4847401,"id":"Q4847401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$27E83346-B4BD-4EBA-9083-3E3004165AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"516714b39f83c68d26c4d317a58012e1d449cd5a","datavalue":{"value":{"entity-type":"item","numeric-id":3094946,"id":"Q3094946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$9CC366B0-A268-49C7-8B3E-9300648DC393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e070597e4e72e0ddfb8bf1003bf1873c1c51c13","datavalue":{"value":{"entity-type":"item","numeric-id":2470462,"id":"Q2470462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$CD81DAD6-13F2-407A-B9F3-C827BFAF7942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"396acdc33a3b1bf924f2404054ebac9512eb7018","datavalue":{"value":{"entity-type":"item","numeric-id":1034528,"id":"Q1034528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$93500C73-285C-4796-9121-09492287E1DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5640924ccaf8a065d9c6733cfbe8aefddd4a0b12","datavalue":{"value":{"entity-type":"item","numeric-id":2998926,"id":"Q2998926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$2930CB77-3A11-479A-96E1-6DF245641950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5147ed3bd9a849672da2b2f8a6ac57cfc622fa6","datavalue":{"value":{"entity-type":"item","numeric-id":3119064,"id":"Q3119064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$6534B819-21BF-4B08-8511-2B3F0ECE760C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80b66174affbbab937e38602a01460e8d985a79b","datavalue":{"value":{"entity-type":"item","numeric-id":5217099,"id":"Q5217099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$42C6E1D8-96F2-44C2-A3FE-315B8880DCD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2645eaa1f95c6416330e6a73adb045fc0bc147e7","datavalue":{"value":{"entity-type":"item","numeric-id":5360763,"id":"Q5360763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$C55F73AF-B175-4125-B02A-0C925AB871DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f7aa99834558606212c92725ef41b8d08d0c68f","datavalue":{"value":{"entity-type":"item","numeric-id":1039431,"id":"Q1039431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$AB895C7B-A149-4C5C-B870-0363584BB158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a73bc2976f46c5974fb593d529461c4ae87697f8","datavalue":{"value":{"entity-type":"item","numeric-id":2250462,"id":"Q2250462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$7F4E47AB-F51C-4F42-BC04-0C665426C06E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2927560395a82fce4f7c7cffd4bcb654877ccac","datavalue":{"value":{"entity-type":"item","numeric-id":4325282,"id":"Q4325282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$0843BD9C-491C-4789-BA26-7C173E1420E9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1c2e20d67973aeaae19ffa59a9b304542a7a0146","datavalue":{"value":"Q130047657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$3D1CEECE-FDD1-4224-8B60-4CC01799B185","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b6c742f6223084efb35634ab296aba93bf916dfa","datavalue":{"value":"10.3390/A11040040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331438$69EE4F0A-91A6-422D-9E2C-F1E56BCB5791","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbb3d2e089bbd93a727a13fc938803deb417fdbe","datavalue":{"value":{"entity-type":"item","numeric-id":2892015,"id":"Q2892015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d39b3308df99ee7385a3d3cd1e52c3e3a4d3b758","datavalue":{"value":{"amount":"+0.853842556476593","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2331438$C365B1A9-316C-4F38-AC31-A625EA049C6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b174da4b118b77a134b2d43c69aa2d6242bb840","datavalue":{"value":{"entity-type":"item","numeric-id":5360763,"id":"Q5360763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cceb95c71281c275ed6fd85d4021d2f859f1e27","datavalue":{"value":{"amount":"+0.7736209630966187","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2331438$90FEFFEE-0E95-4470-875D-D437476582A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f67ef93d27a64574d9f82f3585b12b70ea739052","datavalue":{"value":{"entity-type":"item","numeric-id":4358434,"id":"Q4358434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60ce1421352b8b9e767b69bd7927765a92b5c41d","datavalue":{"value":{"amount":"+0.7425109148025513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2331438$A9E6B846-6B82-426E-8D15-2CF414A9554C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39a93210973aa96391641d5ad0dae8c539ad81fa","datavalue":{"value":{"entity-type":"item","numeric-id":3804715,"id":"Q3804715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b44b23a7e9e447d91559646e4cb4ad09b4295a2c","datavalue":{"value":{"amount":"+0.7393418550491333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2331438$828B3E9C-0DC9-443A-BE19-014653DF9CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76de0a0256e69778f052b5a9d9ae0fa0f11c416a","datavalue":{"value":{"entity-type":"item","numeric-id":3323979,"id":"Q3323979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88a56211bff7d1bd5ec428dee9c31afc2e10f732","datavalue":{"value":{"amount":"+0.7345356345176697","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2331438$0ACBDAB1-3EF8-422D-99AC-84061923282A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331438$89D089E5-5EC0-4F32-BE9C-70ACD09F080B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2331438","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2331438"}}}}}