{"entities":{"Q2065883":{"pageid":2076625,"ns":120,"title":"Item:Q2065883","lastrevid":57709218,"modified":"2026-04-01T00:46:03Z","type":"item","id":"Q2065883","labels":{"en":{"language":"en","value":"Recolouring weakly chordal graphs and the complement of triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7456575"}},"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":"Q2065883$70C39853-58F6-4927-A73D-67A5CEC4A584","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5edacfd1d708119a06a6889e8cebcf5fc0771030","datavalue":{"value":{"text":"Recolouring weakly chordal graphs and the complement of triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2065883$FD95E5CC-84C5-4336-A1F4-82BEF7870438","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9c3ad955557f6af89fcf0cd9f0888a7f5584f213","datavalue":{"value":"1485.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2065883$991E391A-2547-43F4-88AD-0D68AF356D46","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bad041c9d1d84faeff5690a467e547848fc3dd4","datavalue":{"value":{"entity-type":"item","numeric-id":2065882,"id":"Q2065882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$F7EE72E2-D1C9-4259-BAE4-7FE896D0231A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$D2347B9D-BE24-4129-A215-BDFD5F15623D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"309b5a9e9d85dbf70bec61362bb05fd1f86a0e81","datavalue":{"value":{"time":"+2022-01-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2065883$49F8B825-41EE-42EF-92F5-4F495BE6DF69","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"32e1410e02d6200504f2a540b7ce4b11c7e4fb7f","datavalue":{"value":"https://arxiv.org/abs/2106.11087","type":"string"},"datatype":"url"},"type":"statement","id":"Q2065883$25DF0810-0532-419B-99A9-C8DBDD37B1CF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"254e341e86c5a71d075d8f0cfbf1bf528c59730c","datavalue":{"value":"Let \\(G\\) be a graph and let \\(\\mathcal{C}\\) be the set of all \\(k\\)-colorings of \\(G\\). The \\(k\\)-recoloring graph of \\(G\\), \\({\\mathcal{R}}_k(G)\\), is a graph with \\(V({\\mathcal{R}}_k(G))={\\mathcal{C}}\\) and \\(c_1,c_2 \\in \\mathcal{C}\\) are adjacent in \\({\\mathcal{R}}_k(G)\\) if and only if there is exactly one vertex \\(x \\in V(G)\\) with \\(c_1(x)\\neq c_2(x)\\) and \\(c_1(y)=c_2(y)\\) for any \\(y \\in V(G)\\setminus \\{x\\}\\). It was showed by \\textit{C. Feghali} and \\textit{J. Fiala} [ibid. 343, No. 3, Article ID 111733, 6 p. (2020); Zbl 1432.05040)] that there exists a \\(k\\)-colorable weakly chordal graph \\(G\\) such that \\({\\mathcal{R}}_{k+1}(G)\\) is not connected. A generalization of this result is one of the main results of the paper. It is proved that for any \\(n \\geq 1\\), there exists a \\(k\\)-colorable weakly chordal graph \\(G\\) such that \\({\\mathcal{R}}_{k+n}(G)\\) is not connected. The result is proved by showing that there exists \\((k+n)\\)-coloring \\(c\\) of \\(G\\) such that \\(\\{c(x); x \\in N[v]\\}=\\{1,2,\\ldots ,k+n\\}\\) for every vertex \\(v \\in V(G)\\), which shows that \\(c\\) is an isolated vertex of \\({\\mathcal{R}}_{k+n}(G)\\).  On the other hand, there also exist \\(k\\)-colorable graphs \\(G\\) such that \\({\\mathcal{R}}_{k+1}(G)\\) is connected. In this paper the author presents another family of such graphs. It is proved that for any \\(k\\)-colorable \\(3K_1\\)-free graph \\(G\\) it holds that \\({\\mathcal{R}}_{k+1}(G)\\) is connected with diameter at most \\(4|V(G)|\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2065883$63A80FB6-EA6D-40DC-9398-635AF8631B5C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"512183e69be4ab0f9c803f93e55f4d9b77753376","datavalue":{"value":{"entity-type":"item","numeric-id":504963,"id":"Q504963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$8666E556-3848-40E1-9E4C-8B5583B45A19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2065883$C112E8CA-93F1-4D9F-8BD8-BC602BA54CA2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"632269d49f669cda65de30935211c0558f4d4972","datavalue":{"value":"7456575","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2065883$1B4ADC20-1978-423A-B4C8-06EF71A14478","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2065883$C37E6DFF-A96D-455D-A66E-6172DF4161A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c3ca57d7e29ab6073aa567c6a395b1f353af0f8","datavalue":{"value":"reconfiguration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2065883$35EA8422-90C0-4B21-80D4-32F71244F903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"478f84e9c3e046bc46ddb3a0fb12fba70158332e","datavalue":{"value":"weakly chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2065883$39D5C8C4-0500-40FC-9FF7-C218D7B0DA12","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":"Q2065883$C77D0D2B-EA13-4105-9EC5-A4785F0FFF09","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0e101ffd4d7bcbf0dd9c1a505cb489b51871da8f","datavalue":{"value":"W3212280926","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2065883$CBB8B9F7-D1B8-4D46-94C1-0B24C5FC383D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f467ee2258248f510c1db08ca6d687d49519ddca","datavalue":{"value":{"entity-type":"item","numeric-id":1686264,"id":"Q1686264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$6BED2EFC-537E-42B4-871C-95C2D6D7F9C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69b6b4c9fe0f79147c5728198272fedbd7bad1d0","datavalue":{"value":{"entity-type":"item","numeric-id":2436666,"id":"Q2436666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$2338E48B-9B6D-4086-A44F-9A88A35F16CD","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":"Q2065883$809C307A-93B2-4D9C-8F5A-24EFB65EB169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$90C2C472-2FB2-44FA-8DC8-85E23BC905CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51d5d33f1c5bb1eab1c4f9bf3cf51c64fd675335","datavalue":{"value":{"entity-type":"item","numeric-id":2286594,"id":"Q2286594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$9295EAB2-7A84-40E6-BA47-4D6BEB1D629A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbe097f62791bcc42fe71dd30e6b393e0a8c6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2553445,"id":"Q2553445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2065883$5ECDD96E-BF82-44C4-B0A6-F37CD98B41A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"70cd2d635bd31d7c8c66567ad3465b836ecbb758","datavalue":{"value":"10.1016/J.DISC.2021.112708","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2065883$9698C955-CB6D-4550-85F3-BB11D62A42AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af105b234abc93583bf161eab2ac28a279aa8d39","datavalue":{"value":{"entity-type":"item","numeric-id":2286594,"id":"Q2286594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f19c7cde7a780e36fbb06a28f17e93a9f0aeffe","datavalue":{"value":{"amount":"+0.7690352","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$E55CE32B-D9E1-4A2E-A0BE-8D40A44DA2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86432ad8469df839c784e577188936f2d875e85c","datavalue":{"value":{"entity-type":"item","numeric-id":3614482,"id":"Q3614482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17d650a0ff2d7eb0c2abb178b95ad9ae2831a2e2","datavalue":{"value":{"amount":"+0.71359336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$0E395646-46E7-4DE8-B18D-FA12CADBC5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee15a76999d01d3d0ae55b95510d0fb8cfae1746","datavalue":{"value":{"entity-type":"item","numeric-id":5298924,"id":"Q5298924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d4617d0c0513899b9716ac1cafe912ba1c83753","datavalue":{"value":{"amount":"+0.70934427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$F6CB913E-DA78-43A6-9497-086DC66F334F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1572aa8ee6efbb11574972261d04bb4008adb0d6","datavalue":{"value":{"entity-type":"item","numeric-id":2643326,"id":"Q2643326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97547a151dc55453cfb6dfda0d71d1bc5769a518","datavalue":{"value":{"amount":"+0.7082498","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$6BB2F164-4866-40E7-B59B-093A606D369F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2245be7be69eb364f3e0a10e3a48b6565b7cf3f","datavalue":{"value":{"entity-type":"item","numeric-id":266706,"id":"Q266706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26611c8c023d12c2bd491650a56c4c50311b1db3","datavalue":{"value":{"amount":"+0.69797313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$0664DB84-C868-4F69-9ABB-AE80B1FB52F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9facf072ba0ae78ce0157af953dd7bca26f96b6e","datavalue":{"value":{"entity-type":"item","numeric-id":4327761,"id":"Q4327761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74a75717e2b3276cb71d3fbf72fc4b522b305025","datavalue":{"value":{"amount":"+0.6945763","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$B303546E-ADED-495E-B882-91D176CDCD60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abe8336c60849d2059ffe66b0eab82cf315de7e3","datavalue":{"value":{"entity-type":"item","numeric-id":2166319,"id":"Q2166319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f166c15e4b5a37eba955420fa94b1ca6c9353d5","datavalue":{"value":{"amount":"+0.6900991","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$6B267457-4A58-469B-A939-1FA6A07EF99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94ba2478656f12dd61d9206cb00cf4bab0678ff2","datavalue":{"value":{"entity-type":"item","numeric-id":2436666,"id":"Q2436666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a1d448e62f6e5fe90e0ae4a02973baa31e67742","datavalue":{"value":{"amount":"+0.6838259","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$1375DD55-B457-47DF-AD53-963AA7CAD4A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15d429babda31aa5b682ee37d80828074601eff5","datavalue":{"value":{"entity-type":"item","numeric-id":2857338,"id":"Q2857338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8b4ae5e1b77c90ca8942acaf46f17a7ad9d7c9f","datavalue":{"value":{"amount":"+0.68055433","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$667BBB53-1028-4008-8216-70E1C5DA6209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79dab8106e1bece7e478f5f5fac286869debf9eb","datavalue":{"value":{"entity-type":"item","numeric-id":1379170,"id":"Q1379170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15de90725895ab763d96195959892f83ff7dcfe1","datavalue":{"value":{"amount":"+0.6790574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2065883$20F0C441-10B0-400A-9361-F59B6DA3C424","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2065883","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2065883"}}}}}