{"entities":{"Q2166215":{"pageid":2176958,"ns":120,"title":"Item:Q2166215","lastrevid":71449800,"modified":"2026-04-13T22:20:33Z","type":"item","id":"Q2166215","labels":{"en":{"language":"en","value":"Colorings of oriented planar graphs avoiding a monochromatic subgraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7574706"}},"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":"Q2166215$B4F05C9C-ECC0-4B4E-9AF0-4C7058C3FE6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"95fd0cd44045eb3d905296e00d7fc08750c60755","datavalue":{"value":{"text":"Colorings of oriented planar graphs avoiding a monochromatic subgraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2166215$DD38DA04-5D34-41E7-9E1D-67EF1390E440","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc1acab4b0542316ed6d5007a2a17bdea4c6fc5a","datavalue":{"value":"1505.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$83A4B790-AEC3-4A56-A685-C2E57BE52EA4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e13e83b8e04307036c9795c24557644d15bb5d51","datavalue":{"value":{"entity-type":"item","numeric-id":832854,"id":"Q832854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$27A31126-EB0F-420B-A403-8513263E34DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"333e7366b859c9d0894f9d970904d38f74882167","datavalue":{"value":{"entity-type":"item","numeric-id":271596,"id":"Q271596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$F85CBBA7-DEBF-4E2A-A103-D097850B9F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4185fab075579741303acd9e5902d7c3541e5c4","datavalue":{"value":{"entity-type":"item","numeric-id":779241,"id":"Q779241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$4B73EE44-6E64-48EC-90B2-715916C18447","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$F0EC6F03-E460-4377-9162-AB41283859F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c763b4bf6aa09d448ee2a1f4c2810cf527282214","datavalue":{"value":{"time":"+2022-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2166215$41DB3B47-52A0-4ECD-B80D-5EE2EA518B7F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cbce1ae28c1f127ef7d18bc3c6a6e19828401c44","datavalue":{"value":"https://arxiv.org/abs/2102.07705","type":"string"},"datatype":"url"},"type":"statement","id":"Q2166215$EC9CE6C1-E7FA-4CB7-A4B9-9FD0BA149A52","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e99ecb86564b33ed7bcb0f7e4820876eda5578e6","datavalue":{"value":"Let \\(F\\) and \\(D\\) be two fixed simple digraphs. An \\(F\\)-free \\(k\\)-coloring of \\(D\\) is a vertex-coloring in which no induced copy of \\(F\\) in \\(D\\) is monochromatic. The authors study the complexity of deciding for fixed \\(F\\) and \\(k\\) whether a given simple digraph has an \\(F\\)-free \\(k\\)-coloring. This is a directed version of the previous problem of determining the complexity of coloring planar graphs avoiding a monochromatic induced copy of some connected planar graph \\(F\\). It can be obtained that for every fixed digraph \\(F\\) whose underlying graph is not a forest, every planar digraph \\(D\\) admits an \\(F\\)-free 2-coloring and that for every fixed digraph \\(F\\) with \\(\\Delta(F)\\geq 3\\), every oriented planar graph \\(D\\) admits an \\(F\\)-free 3-coloring.   In this paper, the authors mainly prove the following two main results. \\begin{itemize} \\item[(1)] If \\(F\\) is an orientation of a path of length at least 2, then it is NP-hard to decide whether an acyclic and planar input digraph \\(D\\) admits an \\(F\\)-free 2-coloring.  \\item[(2)] If \\(F\\) is an orientation of a path of length at least 1, then it is NP-hard to decide whether an acyclic and planar input digraph \\(D\\) admits an \\(F\\)-free 3-coloring. \\end{itemize}","type":"string"},"datatype":"string"},"type":"statement","id":"Q2166215$B48DB330-6FAD-4F1E-AC2C-88C385375DD3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9df295c593cdafda807b45ad7f4f86b874cf4fa5","datavalue":{"value":{"entity-type":"item","numeric-id":251537,"id":"Q251537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$70600077-90D4-4DC1-9BE7-0B74AE2511AC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$446946D7-E7C4-4780-948A-D394B6F1915F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$0A4BF99B-A7DF-4A4C-BCBD-BCA2951E7C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$C86B5F1D-1777-4A8C-958F-9A5B28164F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$8192ECA6-482B-4A78-A3FE-EFCA8FC294BB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3105f29115288eef1c0885e20e3ee6281a04c09","datavalue":{"value":"7574706","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$6A8A4AB2-6F25-4B28-82EB-1901F4D7CF47","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92491b612f9666e05ce4e8c57837d911db50179b","datavalue":{"value":"digraph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2166215$4CA3169B-C053-4DC2-86BD-DB70C65888E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3dd931642384fb57a8dd805071ac40dd0c1a29c","datavalue":{"value":"planar digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2166215$1E631738-9B0E-4871-9F9B-C3BEA06A85CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2166215$E98EA1C3-2BD2-48F9-BFC9-DB97194AD0F9","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":"Q2166215$55037045-9625-475A-99BC-6E033C52319F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bdbbc3561dec02b3a94c483e729f0685b5f8aaa2","datavalue":{"value":"W3129896241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$12611049-C5BF-43B5-9FDB-C17F6FF18333","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7222b7128910c79c75ce187afd05199714404b6f","datavalue":{"value":{"entity-type":"item","numeric-id":2498403,"id":"Q2498403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$E36287FF-098A-4259-9C9C-A15BB5EAC45A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"113786d2d19b2791b4ab0efc5d37fb5bcd1db102","datavalue":{"value":{"entity-type":"item","numeric-id":1412662,"id":"Q1412662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$DF2048F0-BBD7-4BA8-9D2B-B091C572758D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c74d2f37295184415006f810370eaa500cb4c6cd","datavalue":{"value":{"entity-type":"item","numeric-id":607000,"id":"Q607000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$9C664F26-CEC9-4B51-823A-A97669ED7A5E","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":"Q2166215$508539A7-9A54-4734-A400-68CB3AB8E375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa74031add566b5d80139688074854a624e830d8","datavalue":{"value":{"entity-type":"item","numeric-id":3484846,"id":"Q3484846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$9F07A5CD-2D22-432C-A875-7888FD00A000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74874caf2bfd1d4103793d6c04774e5df52ea971","datavalue":{"value":{"entity-type":"item","numeric-id":1907105,"id":"Q1907105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$C3CD0AB0-5222-4129-8A8D-2ED05D4AE5B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"820f43e838f36e4751380bfd28125ba71c80d275","datavalue":{"value":{"entity-type":"item","numeric-id":958693,"id":"Q958693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2166215$517674FA-DD40-40B4-A6B0-CE8FA432E757","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd01a605419f7099fab2f26ac10a17eb3015145f","datavalue":{"value":"10.1016/J.DAM.2022.05.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2166215$0E608AEE-E6D2-4E61-8DDE-1F9648339DB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e956999cc5fcc115e47b78bd0e17cbd7851bb776","datavalue":{"value":{"entity-type":"item","numeric-id":2498403,"id":"Q2498403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"606019c6330f7ea02aef8655167f4c2d00fee988","datavalue":{"value":{"amount":"+0.8460158705711365","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":"Q2166215$4F2804EF-63B3-4D62-AB2F-80C1CEEA4B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ce25dab7344199e92582402896013c1e51a6019","datavalue":{"value":{"entity-type":"item","numeric-id":3046488,"id":"Q3046488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ccb90f8649f7634fc478872fea2adabb596d8e5","datavalue":{"value":{"amount":"+0.8147178888320923","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":"Q2166215$5E60DF43-6045-4A8F-BE69-820F1C0DEE7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ae76b706935bd7e0522596726e2ec67342ff7d2","datavalue":{"value":{"entity-type":"item","numeric-id":897592,"id":"Q897592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4777b54ed4164548b4c263254ee6d5c37cdee4c1","datavalue":{"value":{"amount":"+0.7871425151824951","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":"Q2166215$8C912E8F-A4F4-4F37-8866-F0BB7FD1D67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecbdb00c4c50ec370e450086013102ec21f79bc1","datavalue":{"value":{"entity-type":"item","numeric-id":476308,"id":"Q476308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0042e13ed7b532457b5de640f74e11889608e06d","datavalue":{"value":{"amount":"+0.7858643531799316","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":"Q2166215$6C43B510-4D18-4D11-8CA2-F2525D41BAE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b17702758061e03e4482f01b99e3f01025ca4952","datavalue":{"value":{"entity-type":"item","numeric-id":2912743,"id":"Q2912743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bde043fbb48a774561c84aa309bc96569b9c415","datavalue":{"value":{"amount":"+0.785031259059906","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":"Q2166215$38ACC75B-2A7D-4A46-ACEC-6F1E6AEF0ADF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Colorings of oriented planar graphs avoiding a monochromatic subgraph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Colorings_of_oriented_planar_graphs_avoiding_a_monochromatic_subgraph"}}}}}