{"entities":{"Q2131856":{"pageid":2142599,"ns":120,"title":"Item:Q2131856","lastrevid":57738150,"modified":"2026-04-01T04:40:34Z","type":"item","id":"Q2131856","labels":{"en":{"language":"en","value":"A polynomial version of Cereceda's conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7514791"}},"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":"Q2131856$0958C5F4-0DDB-4898-92A2-1715F0896149","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ff3931e87180b4339a077f1473c26c8536c2b05","datavalue":{"value":{"text":"A polynomial version of Cereceda's conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2131856$24980D17-07CA-459A-9170-86E43CAB8A8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64628f216a74e7c15b5ded630aeef817932f3aac","datavalue":{"value":"1493.05096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$D5AC505F-6BF7-4430-A72B-A75B302EF827","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebc3e32045f9761c31fcd6202016ff847b18bae9","datavalue":{"value":{"entity-type":"item","numeric-id":512580,"id":"Q512580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$F95E755C-255F-41C7-B21E-D305F7367072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71d5353733bf428859a06fce541c6f739a6abd71","datavalue":{"value":{"entity-type":"item","numeric-id":683755,"id":"Q683755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$88DA62BA-90CF-4DCA-A05C-76904335526B","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":"Q2131856$5964DB6F-774D-41E7-95ED-B7DD15ADFA18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb92150f4e7ba6ad94427d659f8564387023a05a","datavalue":{"value":{"time":"+2022-04-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2131856$962E65C5-2DA0-4C64-A5F1-8324ED9FDC85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a3269138a747110589d9c4e3cb7e9429aaae9e8d","datavalue":{"value":"https://arxiv.org/abs/1903.05619","type":"string"},"datatype":"url"},"type":"statement","id":"Q2131856$44E3D4E6-BC5F-422A-A9EC-322B2FC957DF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b29dcfef92eb3e53abf1ad35b76ba626591f8d47","datavalue":{"value":"A \\(k\\)-coloring of \\(G\\) is a function \\(f\\colon V(G)\\rightarrow \\{1,\\dots,k\\}\\) such that the coloring is proper. The \\(k\\)-reconfiguration graph of \\(G\\), denoted by \\(\\mathcal{G}(G,k)\\), is the graph whose vertices are \\(k\\)-colorings of \\(G\\), and two \\(k\\)-colorings are adjacent if they differ on exactly one vertex. A graph \\(G\\) is \\(d\\)-degenerate if any subgraph of \\(G\\) has a vertex of degree at most \\(d\\). It is known that for any \\(d\\)-degenerate graph \\(G\\) and every \\(k\\ge d+2\\), \\(\\mathcal{G}(G,k)\\) is connected. \\textit{L. Cereceda} [Mixing graph colourings. London: London School of Economics and Political Science (PhD Thesis) (2007), \\url{http://etheses.lse.ac.uk/131/1/Cereceda_Mixing_graph_colourings.pdf}] conjectured that the diameter of the \\((d+2)\\)-reconfiguration graph of any \\(d\\)-degenerate graph on \\(n\\) vertices is \\(O(n^{2})\\). So far, there is no proof of a polynomial upper bound on the diameter, even for \\(d=2\\).  In the paper, the authors prove that the diameter of the \\(k\\)-reconfiguration graph of a \\(d\\)-degenerate graph is \\(O(n^{d+1})\\) for \\(k\\ge d+2\\). Also, they prove that if \\(k\\ge3(d+1)/2\\), then the diameter of the \\(k\\)-reconfiguration graph is quadratic, improving the previous bound of \\(k\\ge2d+1\\). Moreover, the authors show that Cereceda's conjecture is true for the \\(5\\)-reconfiguration graph of planar bipartite graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2131856$D45DE54B-4902-4AE9-A6CB-2D8D828E824C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5b4a08ebcb49ac474f1089f0ed600b622e583db1","datavalue":{"value":{"entity-type":"item","numeric-id":292238,"id":"Q292238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$E55BA1DB-FC4C-4D18-BDE6-18E166B29077","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$A69217B8-EBEB-4D25-A159-883FAC110F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$35036220-9FF6-454D-8D90-CDC5265978E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$86C75211-44B9-4580-93E4-20665ABD222B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$9A382C75-41AF-4EAA-ADBC-59831C8ACC52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$905AD055-7E65-473E-B905-DF206112A353","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52857fbdc326094f6f981ab544a475f319137965","datavalue":{"value":"7514791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$38E6A127-6C51-4882-AB07-0CCC85F2A4C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c3ca57d7e29ab6073aa567c6a395b1f353af0f8","datavalue":{"value":"reconfiguration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2131856$9BE32D53-9557-4BFD-ACEA-17204A756EFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2131856$C8867FFC-1992-4F85-9098-373E93E6BD25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4d3c1c809c084ef9146ad2fbed7c52b7f7e54dc","datavalue":{"value":"Cereceda's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2131856$DC1438A7-9F63-4281-8103-45FD01F3D3C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0058e45451e14100b8e3d344c404bce66d5836c","datavalue":{"value":"degenerate graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2131856$8F4F14DC-F8E4-47DA-B352-0C4136510B6B","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":"Q2131856$DE1E69A2-7CD9-4697-8473-75103A776BBB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a4c3ae319e15424c0bafe0807550a7df2dc893a2","datavalue":{"value":"W4210673793","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$C507D257-8DCE-4C7D-8F17-D38D5C90F604","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":"Q2131856$C2A8429E-69C5-46CC-84D9-ABD6D1FF97DD","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":"Q2131856$BFA7DDA6-375D-44CF-A55C-D6BC53637157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4a6568cd26f3384c3bc980d1e62369b84726d64","datavalue":{"value":{"entity-type":"item","numeric-id":4993126,"id":"Q4993126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$AA5227AA-A58A-4C01-B5C0-1C304054355F","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":"Q2131856$0082582B-CA38-42D6-B557-4DBED3307888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62fd8e8936ae5e996a9e7264bf82bdfe33fd745c","datavalue":{"value":{"entity-type":"item","numeric-id":1699301,"id":"Q1699301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$49DF9E2A-995F-4CB6-B12E-81929A87FA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78a775ff9d216f51dea46e921f3ca629caac6188","datavalue":{"value":{"entity-type":"item","numeric-id":896058,"id":"Q896058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$9A079B67-B393-444D-B2F1-C8538CD3C56B","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":"Q2131856$B0E81AA1-92C1-4E94-868B-F3F266728E6D","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":"Q2131856$9D1793CA-6655-40B8-9F2F-FF45BF264BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d3ab055106f797fe01aaa28a41601bd3cca4b22","datavalue":{"value":{"entity-type":"item","numeric-id":5236321,"id":"Q5236321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$9E095CC6-7260-40FA-A1BB-CFF78931324D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$31668BBC-E7EF-4747-9231-2CB2DDC7A7F6","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":"Q2131856$9BA97F1C-7366-4D3A-8153-C4D0C292E9B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ad76f20a0c68a281089dc2ebfd395083347111","datavalue":{"value":{"entity-type":"item","numeric-id":5110690,"id":"Q5110690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$89FEBBF4-10EB-45C3-B4C0-63E0CAD7AF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1eeb19484b4915ef5ca059d67a4d95a28cbbf0","datavalue":{"value":{"entity-type":"item","numeric-id":1621073,"id":"Q1621073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$0F122E0E-06FA-459D-B17A-B735793E4E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f03e9decc285b6fbd0050b6f231d4839172602c","datavalue":{"value":{"entity-type":"item","numeric-id":2657051,"id":"Q2657051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$436C1F75-3E52-4607-BF19-66E47B5FAECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48894ab61348acabec1fe6f1395b76b38297e77f","datavalue":{"value":{"entity-type":"item","numeric-id":2833252,"id":"Q2833252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$87BDCBD5-9283-4D40-9837-2818B198C48E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d44da53bb2807d29f97c236ce74b8ca1cb8debcc","datavalue":{"value":{"entity-type":"item","numeric-id":3447279,"id":"Q3447279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$F113114D-96C4-4D09-A36F-C2D8ABA749BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fc00f68d01a683da71ebdbf42254dc69e2487a1","datavalue":{"value":{"entity-type":"item","numeric-id":2331456,"id":"Q2331456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2131856$C7395124-001B-42C0-864B-75ABEB229EA5","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":"Q2131856$B9240D75-C39E-4D09-9192-9343E37706B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b92a091d9395ab8260a8e597e6025d20cbd4f26c","datavalue":{"value":"10.1016/J.JCTB.2022.01.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2131856$C309217C-FB79-48CB-9352-40B79A923D4C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aafd42753d9908e7d3705cf0142837ee72e96536","datavalue":{"value":{"entity-type":"item","numeric-id":5110690,"id":"Q5110690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"771e1355aab2f128e6aa72280f0d620e002c29c1","datavalue":{"value":{"amount":"+0.91519695520401","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":"Q2131856$29ED5083-62ED-4181-9713-5280B0D8F5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f31a41d8e72e3403e7721d9709c254f8bf7092e","datavalue":{"value":{"entity-type":"item","numeric-id":2657051,"id":"Q2657051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6750f618fc040375aaca891e5c5be41df432a7bb","datavalue":{"value":{"amount":"+0.8830918669700623","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":"Q2131856$919D9DD3-DE23-4D2D-AC2C-1AA43F9FC197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"770b74a926ebe4f9d54d14e80719d51cf51f1278","datavalue":{"value":{"entity-type":"item","numeric-id":1621073,"id":"Q1621073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28bf0ec3816867f578d6852f1ff7abc3f22451bd","datavalue":{"value":{"amount":"+0.8393683433532715","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":"Q2131856$B3680988-6149-4C15-9635-C11C6388B9E5","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":"22fc60584867fb127f49b81cba14e23f94131c57","datavalue":{"value":{"amount":"+0.836033284664154","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":"Q2131856$9E334970-4CEE-4426-B1CC-8AA28190DA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d963e6ae2c5263f96e0ed29193cecd41a5e0fb1","datavalue":{"value":{"entity-type":"item","numeric-id":896058,"id":"Q896058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"266144516531286e25dd67628c6c57c502191c4f","datavalue":{"value":{"amount":"+0.8320531249046326","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":"Q2131856$98F5B0B5-0745-4809-8B80-F0A6BC124EEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2131856","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2131856"}}}}}