{"entities":{"Q6146501":{"pageid":13280808,"ns":120,"title":"Item:Q6146501","lastrevid":58722264,"modified":"2026-04-06T11:33:49Z","type":"item","id":"Q6146501","labels":{"en":{"language":"en","value":"Digraph redicolouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7799826"}},"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":"Q6146501$BDC07879-0A71-4A9A-9AFF-C9E7C4081408","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"061bddfd1830d9fc55ce6e123b3c5595b97094d9","datavalue":{"value":{"text":"Digraph redicolouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6146501$DB52FBD2-649C-493E-8C69-9AEE7F1D31C4","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":"Q6146501$7E9185B5-26AB-4B19-AA2F-FDF7075EB000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4e8471076b9574779be9b69bcf04a02e8ebd18d","datavalue":{"value":{"entity-type":"item","numeric-id":186133,"id":"Q186133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$E1AFE112-14B1-49C3-AC2C-D382965A2C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb42e0bc4d37528b917c4e628531b6cae8003e2f","datavalue":{"value":{"entity-type":"item","numeric-id":299057,"id":"Q299057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$5C09BC23-BDC8-438F-A52C-E99A105D5128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"50dc6921acae0a304a1e6ef9bf5f697588e7095c","datavalue":{"value":{"entity-type":"item","numeric-id":2079879,"id":"Q2079879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$89C67B92-9F56-4505-A0CC-099689C42801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72029dc6de60ee3323426fd93bebcbd8fee7570b","datavalue":{"value":{"entity-type":"item","numeric-id":2093573,"id":"Q2093573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$9C126D22-0518-4091-9F11-27BD2676188C","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":"Q6146501$483709C1-2143-402C-8087-8124FEF3F0E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"36c2e1616da38323cf7ff49255652cb2a9eb6fc6","datavalue":{"value":{"time":"+2024-02-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6146501$A02567BE-988B-461E-B4FB-25E58C46CE9F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3acd11737497da608ce4c1b3b0efedc9d801fe8c","datavalue":{"value":"https://arxiv.org/abs/2301.03417","type":"string"},"datatype":"url"},"type":"statement","id":"Q6146501$165BB4A9-0387-4D18-9978-9DAECF34BCA9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a69c0a7af9a41939d45cfc5c3616e0e9444fb9b","datavalue":{"value":"The authors extend several known tough results concerning dicoloring of graphs and also raise some new conjectures. First, they establish that given two $k$-dicolourings of a digraph $D$, it is PSPACE-complete to decide whether one can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step even for $k=2$ and for digraphs with maximum degree 5 or oriented planar graphs with maximum degree 6. They pose a new conjecture which is an analogue of Cereceda's conjecture for digraphs [\\textit{L. Cereceda}, Mixing graph colourings. London: London School of Economics and Political Science (PhD Thesis) (2007)] and generalized it to digraphs with two new results supporting Cereceda's conjecture. Further, for the restricted version of oriented graphs, they prove that the dicolouring graph of any subcubic oriented graph on $k\\geq 2$ colours is connected and has diameter at most $2n$. They also raise an open conjecture namely ``every non-2-mixing oriented graph has a maximum average degree of at least 4'' to the graph theory community by proving it for the special case of 2-freezable oriented graphs. They also show that every $k$-freezable oriented graph on \\(n\\) vertices must contain at least $kn + k(k-2)$ arcs and a family of $k$-freezable oriented graphs that reach this bound. For the general case, they prove a partial result that every non-2-mixing oriented graph has maximum average degree of at least 7.2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6146501$888441C2-959A-44B2-AEF7-2D7A7BAD17EF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$45F629C1-0DBD-432D-B679-48271D55D056","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6146501$D1F90960-D46B-4ACD-9B3A-C1116C493065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6146501$7088B4A2-8F76-407B-A397-C00DCF767F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6146501$0663FC82-1ABD-424C-A12B-94C34BCCEE3B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8786240050e13005679032cd3a977b780cdd8761","datavalue":{"value":"7799826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6146501$059B2930-1E88-4309-B72C-C412266FB03E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5065cf498479fc02f9dfb256584108521ac2820","datavalue":{"value":"dicolouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6146501$9317A9E1-B1D3-44AF-922B-561EEDA207DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"120fcf9fe0b0e86b9971d62f7689c231474a080b","datavalue":{"value":"recolouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6146501$B07CB349-2E6C-42C1-BA8F-37BA8694A2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bf97e7db59e5ec7914dd2ca1cc94a2bca0e081","datavalue":{"value":"oriented digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6146501$06B1C773-7D64-47E1-9955-6B10A6C7FEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f89b94f7954737975c180ec4b17340d7ea6e90fa","datavalue":{"value":"subcubic oriented graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6146501$1D8D5994-7F43-4AD8-9A01-B655152AA154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a247b8d50f3b59e521a29d7cea05378f7792edfe","datavalue":{"value":"$k$-freezable oriented graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6146501$A852C1A2-B627-4539-8B14-EDA04857E919","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":"Q6146501$90C77BAF-89EF-456C-B874-D529A60425AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"885415d64e56733171380fb21b7a3a668141ac26","datavalue":{"value":{"entity-type":"item","numeric-id":1792087,"id":"Q1792087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$A8F121DF-38C4-449C-AF61-77B0B3580AF1","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":"Q6146501$10602E25-F892-4F34-94F9-A028A488C169","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":"Q6146501$6364F84A-D089-4A29-BBF3-B8C31242C0F1","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":"Q6146501$067B9127-13F1-41CB-9A9B-9FEBBF6F93C7","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":"Q6146501$91009B79-3F6E-4D6E-849A-6ECFFBBF418C","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":"Q6146501$C6397967-ADBC-458C-AD3B-9BD3C9670D51","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":"Q6146501$18DDAD87-A84F-4DE4-89F8-6C28FBA38B51","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":"Q6146501$64BDC639-83AF-4BDF-B5DF-3068449E24ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e184195c5a8284dcbf17831e106578831ea79773","datavalue":{"value":{"entity-type":"item","numeric-id":2570127,"id":"Q2570127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$B4CD871E-87B0-443B-BC3A-79A8855DCEA0","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":"Q6146501$EEA6A746-506B-46C7-B58E-6AB4A8F36E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72da18949a8e896989d957f0a6fe3d834d35231d","datavalue":{"value":{"entity-type":"item","numeric-id":1894370,"id":"Q1894370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$C75FB72B-F859-490E-A720-5639B6EE7E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3ed573aab1340e3f01f3d7d04ea69b64bec434","datavalue":{"value":{"entity-type":"item","numeric-id":1836671,"id":"Q1836671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$FA04F789-C48E-4FEE-9C0D-FE13BB467F04","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":"Q6146501$186636F2-13B3-4B5E-BD0C-D42CFD7AB1DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6146501$2FCE2813-0FAC-4837-9CD4-F77882413043","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a47648a78d919245dcdb5858ece0003943afc913","datavalue":{"value":"10.1016/J.EJC.2023.103876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6146501$C7235428-2B61-4497-A7F5-A71122D7E9C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b837798e1db708f4926ddf8afe67a8a5fd8ace","datavalue":{"value":{"entity-type":"item","numeric-id":6201022,"id":"Q6201022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e4d8165ba3faae1c4a27412ba930190e28afdcb","datavalue":{"value":{"amount":"+0.8430792689323425","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":"Q6146501$D2BD79D9-3745-4CE6-90C7-7375BC541E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0705f7bef23e983d7889b0561c927c5ffe3ebadd","datavalue":{"value":{"entity-type":"item","numeric-id":6585259,"id":"Q6585259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"420c675dbf00392181ee8684cfbcd1920751d151","datavalue":{"value":{"amount":"+0.8320509791374207","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":"Q6146501$3AEDD511-09A0-4FC0-94D0-36388FC92B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"793ab0e3206040ae4389ee420a45d1b7b5aff207","datavalue":{"value":{"entity-type":"item","numeric-id":2131856,"id":"Q2131856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a487a2de1add857ed9f3772bf22cfa445ccce8fe","datavalue":{"value":{"amount":"+0.7768486142158508","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":"Q6146501$9603AB61-4300-4FC8-98F4-9EFDC9CC7F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19539c3e2c53121fe988a16aa4b5415f8d6e4797","datavalue":{"value":{"entity-type":"item","numeric-id":2094875,"id":"Q2094875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb89795938c2922cf7b5c773b6696a3dd0e76487","datavalue":{"value":{"amount":"+0.7615319490432739","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":"Q6146501$DBE7C235-7310-42BA-BF3A-0E6D37413F15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6146501","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6146501"}}}}}