{"entities":{"Q2145762":{"pageid":2156505,"ns":120,"title":"Item:Q2145762","lastrevid":73490898,"modified":"2026-04-14T16:12:06Z","type":"item","id":"Q2145762","labels":{"en":{"language":"en","value":"List-recoloring of sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7544369"}},"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":"Q2145762$3430EA5D-18D9-40EF-977B-16F5D1AF5EE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b73c2ffa291fe2c7610e48b208bd82b21fa4959","datavalue":{"value":{"text":"List-recoloring of sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2145762$4C8BD257-2284-4530-8AC9-AF13C0418270","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2193742929207b3d9ba5306be6a0a2ad77a511c1","datavalue":{"value":"1492.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2145762$8DEA7716-AF05-4AA0-8DE7-0C47ADD1D101","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae41f04ca594ca85b65fe9b038c9fd67cd961e89","datavalue":{"value":{"entity-type":"item","numeric-id":311578,"id":"Q311578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$99EFD866-A1DD-40FF-BCDE-0CE59324A75E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$1527AB97-474B-43A6-A550-026C414F9ACD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95e580f4051f5bb4afafd11f30b01e18c9a41ef8","datavalue":{"value":{"time":"+2022-06-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2145762$19BBCEA1-78E8-4F63-9F60-4F6AEE190E56","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d9f32326cf9dee6c637cffa3ffc5c7f0059968e1","datavalue":{"value":"https://arxiv.org/abs/2201.05133","type":"string"},"datatype":"url"},"type":"statement","id":"Q2145762$93E36925-8F14-449F-92BA-D86815ECA026","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2477031cf0f7848bc18404775181ae73e77e0e50","datavalue":{"value":"For a list-assignment \\(L\\) for a graph \\(G\\), and \\(L\\)-colorings \\(\\alpha\\) and \\(\\beta\\), an \\(L\\)-recoloring sequence, starting from \\(\\alpha\\), recolors a single vertex at each step, so that each resulting intermediate coloring is a proper \\(L\\)-coloring. In this paper, the author proves that there exists an \\(L\\)-recoloring sequence that transforms \\(\\alpha\\) to \\(\\beta\\) and recolors each vertex at most a constant number of times if (i) \\(G\\) is triangle-free and planar and \\(L\\) is a 7-assignment (at most 30 times), or (ii) mad(\\(G\\)) < 17/5 and \\(L\\) is a 6-assignment (at most 12 times) or (iii) mad(G) < 22/9 and \\(L\\) is a 4-assignment (at most 14 times), where mad denotes maximum average degree. Parts (i) and (ii) confirm conjectures of \\textit{Z. Dvo\u0159\u00e1k} and \\textit{C. Feghali} [Electron. J. Comb. 27, No. 4, Research Paper P4.51, 21 p. (2020; Zbl 1457.05033)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2145762$CD620A3D-C290-4331-A9E8-AD88561C8904","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2145762$E14984B5-B198-4976-A771-437A21C9633B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2145762$BF69BDF7-F003-4E66-85F3-020291FA057D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94c72db898a9b49b93e66bf1fd76b0d7a20f11c9","datavalue":{"value":"7544369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2145762$5AE816AD-4D3E-4F5A-A11A-49FAB7F010F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc6c835af75a1980578da5eee06f407520c1c556","datavalue":{"value":"list-assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q2145762$4A7F1808-9948-4D43-B180-02B964C2CE99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d636ab7b8544186ea0487dc95d6075fc70127899","datavalue":{"value":"\\(L\\)-recoloring sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2145762$6F665BBB-EE56-48D4-B726-86CF1F2A2D08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abb3f5ef5bfe0d22c9079f4c5062a5ca51d55e34","datavalue":{"value":"maximum average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2145762$B73EF44C-6381-436F-9931-C9D889BB2C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16ab1ba82f7277565a15d9818ac4d6000ac80868","datavalue":{"value":"triangle-free planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2145762$37D55AAE-44B9-479D-ABAC-4872128C241C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$FEF3A1B0-9ACC-4CFE-A33D-22D851AC32EC","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":"Q2145762$8CDDF5F7-477D-484C-AE55-5C96E7E045E5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"165d87aa632d6e4781e0f3522c8494139c07c80e","datavalue":{"value":"W4280629867","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2145762$06C70095-CBCD-4109-8D7A-332434942E68","rank":"normal"}],"P223":[{"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":"Q2145762$2BDE28A3-4E3D-49FF-AE07-1CAB99AFE1E4","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":"Q2145762$6883F8BE-AFE3-486F-B181-6065BA5D9588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36b35a6e194e0f5f82523152ab60e30a56b50aae","datavalue":{"value":{"entity-type":"item","numeric-id":2033925,"id":"Q2033925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$A7EA9944-6D71-47FE-88D1-48DF7F5A2595","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":"Q2145762$C4A15EDF-19C1-41F2-A704-1BA7BB59A086","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":"Q2145762$C925C02B-DC02-4B78-B670-FA34EEA7B990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca748814a26c3d85f0589140752700a15c5d13fa","datavalue":{"value":{"entity-type":"item","numeric-id":2222045,"id":"Q2222045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$3713C4D0-DABD-448D-9EB2-84122B493EF4","rank":"normal"},{"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":"Q2145762$C780A90B-305A-4AD2-A9C0-233C1FC12778","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":"Q2145762$62EECEE3-3C32-47D9-A709-48A6B24C638D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d144fb9cfb96241c16a227de66993feb106c3322","datavalue":{"value":{"entity-type":"item","numeric-id":2131856,"id":"Q2131856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$A5E089E7-DF57-43B8-BC51-0D0744A8CEA4","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":"Q2145762$2D5CFAE9-1B71-4925-AB8B-C7045565982A","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":"Q2145762$EDFFBC48-4F00-4549-911F-E7619B5DBADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee2264ad6b975890c81d95c9351986d136c9ee1f","datavalue":{"value":{"entity-type":"item","numeric-id":2223443,"id":"Q2223443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$D7F2A7DB-236F-4F57-AF00-A698C82438C9","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":"Q2145762$816A230F-228B-444A-A2FD-0C04EF481DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9909efc85e4f736c7b118b9c1193d126544ade77","datavalue":{"value":{"entity-type":"item","numeric-id":2275448,"id":"Q2275448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2145762$434EC993-EF77-4B27-B9C9-49238F976BEC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b6b4b0a00e53d8422ff61b51791dafbefa0c7842","datavalue":{"value":"10.1016/J.EJC.2022.103562","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2145762$75B58C13-3AAC-4EAD-89A0-49341E560440","rank":"normal"}],"P1643":[{"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":"1902724003c9878ee9f62e79eaaee3fcd4c529cb","datavalue":{"value":{"amount":"+0.8474611043930054","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":"Q2145762$86AEF29C-4903-4179-A43C-649BCA23BA06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b38075a33a97d5ce99a698b3429d2e95c6af30c","datavalue":{"value":{"entity-type":"item","numeric-id":713316,"id":"Q713316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebf8ab19f557441ca026794d7130d264b1e2e53b","datavalue":{"value":{"amount":"+0.7922366857528687","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":"Q2145762$B4B0A81D-6C8A-42FA-AB4B-61B3FC485F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92fb272198f2124ab41cb1a7958a5a66237004db","datavalue":{"value":{"entity-type":"item","numeric-id":3183470,"id":"Q3183470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0a878c1c50983008c44cdf0d161c95916404514","datavalue":{"value":{"amount":"+0.7895122766494751","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":"Q2145762$6AE0EA54-FF34-425E-8EB7-A5DD517EF3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a0d421bc57fd03063efaa55bba8c595f976cf8c","datavalue":{"value":{"entity-type":"item","numeric-id":5199147,"id":"Q5199147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b32216f52061cf7a93cba9d095d3f080c22d7cc1","datavalue":{"value":{"amount":"+0.78600013256073","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":"Q2145762$D19ABD68-547D-462A-BEBD-82509E5D9628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fa78b4155397de2abdbfe1849948d660194eba3","datavalue":{"value":{"entity-type":"item","numeric-id":2084788,"id":"Q2084788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bbdcb69671c746aae07116ef9b1a1c040a62fdd","datavalue":{"value":{"amount":"+0.7836964130401611","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":"Q2145762$2D5F16DE-D2F2-4670-850B-37C1AEEBBD2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"List-recoloring of sparse graphs","badges":[]}}}}}