{"entities":{"Q2657051":{"pageid":2667794,"ns":120,"title":"Item:Q2657051","lastrevid":57975447,"modified":"2026-04-03T07:37:13Z","type":"item","id":"Q2657051","labels":{"en":{"language":"en","value":"Reconfiguring 10-colourings of planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7324235"}},"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":"Q2657051$C6F67A60-8866-48CF-86D6-878C575F1244","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66b94678bd80b59e6b5a0ec8c7cceac8522387b6","datavalue":{"value":{"text":"Reconfiguring 10-colourings of planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2657051$3A40E7C0-FBDD-41F8-A691-7D985C42E604","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ce56e512dd753884528a35099c849f9e808c2f2","datavalue":{"value":"1462.05137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2657051$DDC03A72-D24E-443D-A3AF-6F0E94A57659","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"867aaaa07446d921ef546013732b2686b8ef8de2","datavalue":{"value":{"entity-type":"item","numeric-id":322235,"id":"Q322235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$95CDC34F-9AD3-4DBB-971E-7B3E18B79716","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$D702B9BA-5A83-4AD1-8752-F0FC401E20A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c44e9e40e16b91f474187fb226cbd1d827ea50c7","datavalue":{"value":{"time":"+2021-03-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2657051$26D4AD3C-CBE2-423F-B933-4632CFF1337C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"615427c24e9b3cd7950f3c055d667931d393c112","datavalue":{"value":"https://arxiv.org/abs/1902.02278","type":"string"},"datatype":"url"},"type":"statement","id":"Q2657051$CFBA5EAC-5F31-4393-92CD-2CACE47F94D8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"90abb3c09c7f38ca2fe58b1107a815f0e3180430","datavalue":{"value":"In this paper, the author considers finite, undirected graphs that do not contain loops or parallel edges. For an integer \\(d\\geq 1\\), a graph \\(G=(V, E)\\) is called \\(d\\)-degenerate if every subgraph of \\(G\\) has minimum degree at most \\(d\\). Trees and planar graphs are examples of \\(1\\)-degenerate and 5-degenerate graphs, respectively.  For an integer \\(k\\geq 1\\) and a graph \\(G=(V,E)\\), a function \\(c:V\\rightarrow \\{1,\\dots,k\\}\\) is called a \\(k\\)-coloring of \\(G\\) if for any edge \\(e=uv\\in E\\), we have \\(c(u)\\neq c(v)\\). Let \\(R_k(G)\\) be a graph, whose vertices are all \\(k\\)-colorings of \\(G\\), and two \\(k\\)-colorings of \\(G\\) form an edge in \\(R_k(G)\\) if and only if they differ only on color of exactly one vertex. The main result of the paper is the following:  Theorem: \\(R_{10}(G)\\) has diameter at most \\(\\frac{n(n+1)}{2}\\) for all planar graphs \\(G\\) on \\(n\\) vertices.  The result of the author deals with a conjecture of \\textit{L. Cereceda} [Mixing graph colourings. London: London School of Economics (PhD Thesis) (2007)], which states that for \\(l\\geq k+2\\) and every \\(k\\)-degenerate graph on \\(n\\) vertices \\(R_{l}(G)\\) has diameter \\(O(n^2)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2657051$B34D222C-DCD9-4E93-A8EB-E1897D3E9971","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2657051$BAF56906-2559-460B-9665-187F65C5CAF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2657051$A63809EF-2C5D-44F6-A4D2-28AA8543FAC8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28afa4773178148f01edbe4eea458c3f00c99835","datavalue":{"value":"7324235","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2657051$2CB36036-CF3F-4DD5-BEF0-C867AEE152BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2657051$3D5DF814-3830-4EAD-8272-282C44F13246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b3686a83f91902821ef3a0bb09a5b69aaf13c38","datavalue":{"value":"reconfiguration graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2657051$8BDBF82D-D45F-4B35-9938-5D9DF70C6999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2657051$8E317802-E1A2-4F9A-8888-0387D0C31B26","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"731d9b2383a66f4ce9d61013e4d86126f6cfd51b","datavalue":{"value":{"entity-type":"item","numeric-id":389445,"id":"Q389445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$22142970-BF71-4C00-8073-92B2F26D237B","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":"Q2657051$A271256E-140C-4CA0-8735-8193CC6F5856","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"54c31a093b8916cba3583109256aca99a8e59f9c","datavalue":{"value":"W3031641564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2657051$942B9FAC-4F0E-4277-9752-D62232D06C42","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":"Q2657051$81A3E625-46E4-4FE1-BB2D-1435DDCCC539","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":"Q2657051$9A92D6F8-5A7F-4FBB-9D7E-1F3F7A53EC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a54c2526b2fcd6b65d2cb3b210f65de29bc6714","datavalue":{"value":{"entity-type":"item","numeric-id":3525616,"id":"Q3525616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$E1352769-F886-46A0-8383-EFFC5A05FBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a660508c44709047f1189264cfc1aff7ce8550ea","datavalue":{"value":{"entity-type":"item","numeric-id":5207462,"id":"Q5207462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$D9883CA6-0B0D-481A-8F23-F860176FFA98","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":"Q2657051$A42C6806-015E-4425-BD83-2EDA1E016F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ecc6449020b64018f7c2dfaa9d0945dc74ec146","datavalue":{"value":{"entity-type":"item","numeric-id":1721933,"id":"Q1721933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$CF92E403-46A3-41DB-812C-30AF8A51D690","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":"Q2657051$625A16D2-A6FB-44E5-8B0C-B5DCBFFC28D3","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":"Q2657051$F9806397-8B76-4C9F-8521-2751133A83F3","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":"Q2657051$B38C00BC-446E-420E-ACB4-94AA476FA0AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e9a01d057f2ac8669e7cac2ad5d67b6775d2fa","datavalue":{"value":{"entity-type":"item","numeric-id":1333334,"id":"Q1333334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$505BB570-9116-47EF-94BB-0C4206BE3AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bec1ea839bbae95cce4f38ddbbba08521d102f9","datavalue":{"value":{"entity-type":"item","numeric-id":1892853,"id":"Q1892853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2657051$E41B8C29-4016-4A44-84D5-0459BDD58003","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":"Q2657051$A22FF8E3-D640-47FB-AC24-B7A8B1E5BD5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"01652dd4ae26918d0ca9648c9e0e0819bdb2b306","datavalue":{"value":"10.1007/S00373-020-02199-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2657051$04E130CD-B8F4-4C9E-B792-0D946AAAD70A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82752904767340a57fdbfee3ce9d6f2e5d671952","datavalue":{"value":{"entity-type":"item","numeric-id":2223443,"id":"Q2223443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fba6ae008ffa75bc5061c8699c9c001db98665d","datavalue":{"value":{"amount":"+0.973478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$3DB78C4D-A973-4FED-8B57-C5FDE9AD19D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dcc5954c636de0808a875c8c56003d35a2629ef","datavalue":{"value":{"entity-type":"item","numeric-id":4843507,"id":"Q4843507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cfc85eb4c5d31a4c4bcf7661eef1d42881a107d","datavalue":{"value":{"amount":"+0.8932621","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$FDC56237-FEA5-494E-9CA5-D68D733DCDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d9abeb25f14b99c32a808085ac0084463d6b21a","datavalue":{"value":{"entity-type":"item","numeric-id":3422127,"id":"Q3422127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41a0a514d28346f9fd197ed2ff89a9860a378e41","datavalue":{"value":{"amount":"+0.8853907","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$83687A23-226E-4A82-B9C8-6EC0B3842914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd41e081ae067afaa0d1b105fe6e15210ed517a6","datavalue":{"value":{"entity-type":"item","numeric-id":6056770,"id":"Q6056770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daf076f44e40afdb09592a79a7b7b281833f5214","datavalue":{"value":{"amount":"+0.87361073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$970677AF-F588-4D50-8A19-E7C34FFB78C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c8a355be3e4272a0fd509dc3274fbe198b24df2","datavalue":{"value":{"entity-type":"item","numeric-id":3798676,"id":"Q3798676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fff106b04bca3ae667df18ac709e5fdafdc7433","datavalue":{"value":{"amount":"+0.8650228","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$ED79E898-03AC-4335-B03B-D1A689914983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"accf72a09c6a1ca364ae69a165d35e538220158c","datavalue":{"value":{"entity-type":"item","numeric-id":5133651,"id":"Q5133651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0f411127af2f0a6dffe04cba1842dc4f037a26c","datavalue":{"value":{"amount":"+0.86501205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$A0C0C243-8A46-47DF-B1E8-E2EE7CD34D7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"454f2cc086a43e99683d6ab4a8735dd7380791b1","datavalue":{"value":{"entity-type":"item","numeric-id":2334079,"id":"Q2334079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcfd8ab52319496c67fde7eb5153779ad0dc0ca8","datavalue":{"value":{"amount":"+0.86266506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$C04435EA-E0BD-4D8C-8658-FE68D899F20C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b63e2e9b19e4a2a3f059573a5a09799c7fcc3925","datavalue":{"value":{"entity-type":"item","numeric-id":625795,"id":"Q625795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46968f11952784fa67551fdd55a2e308ff42876f","datavalue":{"value":{"amount":"+0.86151445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$9F909D9C-020F-4381-B9E7-16E44A8B0F18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0c9dcc7f408f1ab43a1cbebc26312659e2f506b","datavalue":{"value":{"entity-type":"item","numeric-id":3517217,"id":"Q3517217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27126872a3cad13a45e1afc5823f2537d49273be","datavalue":{"value":{"amount":"+0.85917115","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$522959C4-423D-4D2D-8446-E1467B361F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c965f42a9f69d89f4eb2cd4f538dc88a0b2c39fb","datavalue":{"value":{"entity-type":"item","numeric-id":2042610,"id":"Q2042610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"342381e87e139e0a967370f7ed16044741de1399","datavalue":{"value":{"amount":"+0.8581873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2657051$B01CD0D7-2CE5-4D6D-8B94-32BECCE5C904","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2657051","badges":[]}}}}}