{"entities":{"Q2680572":{"pageid":2691315,"ns":120,"title":"Item:Q2680572","lastrevid":57974328,"modified":"2026-04-03T07:31:00Z","type":"item","id":"Q2680572","labels":{"en":{"language":"en","value":"On Vizing's edge colouring question"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7637906"}},"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":"Q2680572$349AA320-A13F-42DD-AA67-8A16066F7673","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9d5ff5e79c31ecf02d8c6bb88588dcb35ebbd2a5","datavalue":{"value":{"text":"On Vizing's edge colouring question","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2680572$2E03C7C3-7F47-4A5C-ADEF-E2323E3C6014","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9808621c600adad83f42868ae6acc9c448c3128","datavalue":{"value":"1506.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680572$95C8AAAD-0CE0-4108-99A3-AAE9151F7CE9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8eb893f819332112e861a74fd4234b6294c868f5","datavalue":{"value":{"entity-type":"item","numeric-id":306249,"id":"Q306249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$E9D202E9-3529-429B-8866-278E0D1FA198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc62afd685bf102abedbb40f59ef20f48a65705d","datavalue":{"value":{"entity-type":"item","numeric-id":2011656,"id":"Q2011656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$640C25A4-9606-47BE-85AF-2A698B89425C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"42d34822cfc8beebd2b4581d3c14e02d3080eff8","datavalue":{"value":{"entity-type":"item","numeric-id":338580,"id":"Q338580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$5EE2A738-33C0-4B22-90C5-DFAFA96B2BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c5b6ed1e69541722a2398152ff99aab24649832","datavalue":{"value":{"entity-type":"item","numeric-id":267212,"id":"Q267212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$56C5D0F8-8682-4709-A918-39A6B07E293C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ac0d033f8d3186cd0f10005a7d03586eb6ea0e2","datavalue":{"value":{"entity-type":"item","numeric-id":2032974,"id":"Q2032974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$66845CE2-2775-4CF6-991F-80D388E31C40","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$F5D1A289-B224-411D-967A-49A98BA501F6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eea63d6b9ca849acf5a3794e122546d7b53759fe","datavalue":{"value":{"time":"+2023-01-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2680572$299FA127-3AEC-4F96-9E6E-61733F2016BF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"418161aee2969604117743c4119086ee6672ac9a","datavalue":{"value":"https://arxiv.org/abs/2107.07900","type":"string"},"datatype":"url"},"type":"statement","id":"Q2680572$3C5A3FE6-B464-4E74-A2C4-F8084FC4EC7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c0ead1039d102c9f9652bc8445562baa5356d6a9","datavalue":{"value":"Given a proper edge-coloring of a graph, a Kempe change consists of selecting a maximally connected two-coloured subgraph and swapping the corresponding two colours, this operation yields a new proper edge-coloring. Kempe changes are an essential tool in the proof of Vizing's theorem that every graph \\(G\\) satisfies \\(\\chi^\\prime(G) \\leq \\Delta(G) + 1\\).  The current paper studies a problem in ``combinatorial reconfiguration'': starting from an arbitrary edge-colouring, it is possible to arrive at a given edge-coloring via Kempe changes? The authors show that given any graph \\(G\\) and any \\(k > \\chi^\\prime(G)\\), any given \\(\\chi^\\prime(G)\\)-edge-coloring can be reached from any \\(k\\)-edge-coloring via a sequence of Kempe changes, under the additional assumption that \\(G\\) is triangle-free. This solves a particular case of a question posed by \\textit{V. G. Vizing} [Russ. Math. Surv. 23, No. 6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680572$4365B3C3-65A5-47B1-BA2D-2BD580656B09","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6c786c862ea96c8431b08bcbc1855c9063fc0aba","datavalue":{"value":{"entity-type":"item","numeric-id":271629,"id":"Q271629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$562C912F-0354-405B-A7E9-73510F5D8066","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680572$37973AEB-D755-4822-88B3-5CE494920FAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"155db2058e48f6d82c20966cd6a9c9f428138924","datavalue":{"value":"7637906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680572$6EB20061-15DD-4862-8470-159C1ACAB2AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c57b92affcb004309363ec03a950a06a95694e2f","datavalue":{"value":"edge-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680572$76FF0D6E-F162-4C9D-AEC2-EF4DECF52C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd4fccd9853df3cb7a1e151557ab17d31dce3b71","datavalue":{"value":"Kempe changes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680572$A55AC87D-57AF-4A70-82C3-895269897A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dcb68366ca572f55c68130475f9d75a379df7e2","datavalue":{"value":"edge-colouring reconfiguration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2680572$00922626-30CA-41EE-AE45-3827B76641D3","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":"Q2680572$FD974520-329B-40B7-BB11-8D7F23608B87","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"730ee7402b08528f03f3ec93d481663f44f33717","datavalue":{"value":"W3185503049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680572$2ECD1B64-774D-4B44-9D8C-F6A9E8D6DFD9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c45e0db8674f94569ca817f6b290a0f8eefd32f","datavalue":{"value":{"entity-type":"item","numeric-id":3188669,"id":"Q3188669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$A7EE54E2-C70E-4877-A67A-D28647D99A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b523537ed1f98389b84f1839c85d93c8108952f7","datavalue":{"value":{"entity-type":"item","numeric-id":1026017,"id":"Q1026017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$36D72A29-1367-4B74-B68B-82EDB32BAAE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7194d089e0c326af2325adc852a1b1ee8e5bdfe","datavalue":{"value":{"entity-type":"item","numeric-id":1719578,"id":"Q1719578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$325D1718-DB0F-4216-8C17-9ECE16346D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$377E38F7-1AD0-4EC7-A083-2D8130C36214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78429906c003bbf0dd36bc1312bbc7972b1d9b1b","datavalue":{"value":{"entity-type":"item","numeric-id":1354146,"id":"Q1354146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$C9AE32A4-EEA5-458B-AC66-1BE313859110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b843fa39f0e0ac15d0c37db9d6b9b42637466b2","datavalue":{"value":{"entity-type":"item","numeric-id":1186590,"id":"Q1186590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$AEA6F56A-5E38-4C33-B46D-9A9534AF79E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c702c99f7c4612fc3bfe0f3f6fb83d321b738fe","datavalue":{"value":{"entity-type":"item","numeric-id":2888891,"id":"Q2888891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$6CA4C93C-2FB4-4E30-AA53-1BE46E29A5EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4d16aba6903b4f3c0341ed3cd50b5f9172ab2de","datavalue":{"value":{"entity-type":"item","numeric-id":3424786,"id":"Q3424786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$0192996D-1AAC-45AC-8ADE-61178FE72D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb1b80e0f8357d645c57a8136b484b7d4dfa813","datavalue":{"value":{"entity-type":"item","numeric-id":5321801,"id":"Q5321801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$D5CF53E7-D4E7-456C-AA69-9CEEAED0673A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7216625bc2c07a03955d740d03079c2cf552faf4","datavalue":{"value":{"entity-type":"item","numeric-id":2719831,"id":"Q2719831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$99EFF5FD-3DE8-4413-B28B-B1F3B3973EB4","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":"Q2680572$2EA2BFAB-E462-4CEF-8009-5286CE07D383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ab420d697951bc8b814dd7b8b56b43399714dc3","datavalue":{"value":{"entity-type":"item","numeric-id":2737884,"id":"Q2737884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$EBE9D4E7-829A-4337-A151-A07A902DF9DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a100fba0ec62de6bee58d0048b8aad392be6aa66","datavalue":{"value":{"entity-type":"item","numeric-id":5587729,"id":"Q5587729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2680572$C066BE78-C4AA-43FB-94CA-DA0736BD185F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e293869711ede8d2e1762a57276c5afbdf4ae0d","datavalue":{"value":"10.1016/J.JCTB.2022.10.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2680572$67E64774-549D-4D77-8F76-22B60D21F142","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e599119d30a2e712471bb2d10057c7386895d17","datavalue":{"value":{"entity-type":"item","numeric-id":5460408,"id":"Q5460408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31781c4ce3e4577368b3289a5538613f8f638a6d","datavalue":{"value":{"amount":"+0.7921051383018494","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":"Q2680572$9939F76D-736F-4E2F-AC5F-7E8C62ABCE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a01115163bf176e666d2343f2d156d7194a847cc","datavalue":{"value":{"entity-type":"item","numeric-id":3188669,"id":"Q3188669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8290a80aba2ccca909153edc33c327e14a1ea8f4","datavalue":{"value":{"amount":"+0.7853502631187439","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":"Q2680572$FCC599A9-9E01-4D61-8FA3-DB5D78FB9552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0ced153acd2b22f78913e253fb8f84343457c98","datavalue":{"value":{"entity-type":"item","numeric-id":2022144,"id":"Q2022144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49af0a787e311b774e271543b8ee0974674d6967","datavalue":{"value":{"amount":"+0.765630841255188","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":"Q2680572$DEC6072D-BD6F-4658-B643-ABFAF736333F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0147147aa96cca115652b482e73164fee10868f4","datavalue":{"value":{"entity-type":"item","numeric-id":5207466,"id":"Q5207466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4696ef3ebf7d83fb705464658894d35cc60dd375","datavalue":{"value":{"amount":"+0.7650842666625977","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":"Q2680572$B9690EED-1AA7-4AFC-A523-F18B91A1623D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec3d729366906574bc8f3a565f262c3be4cb4bd5","datavalue":{"value":{"entity-type":"item","numeric-id":3342598,"id":"Q3342598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28e80113d045f46c4cf76f84964fd9ff61541b0c","datavalue":{"value":{"amount":"+0.7646090984344482","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":"Q2680572$5144C2D1-8685-4780-8697-67D2B323C50A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2680572","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2680572"}}}}}