{"entities":{"Q2260631":{"pageid":2271374,"ns":120,"title":"Item:Q2260631","lastrevid":57806769,"modified":"2026-04-02T15:00:55Z","type":"item","id":"Q2260631","labels":{"en":{"language":"en","value":"Near-colorings: non-colorable graphs and NP-completeness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6413661"}},"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":"Q2260631$E05A823A-F9D8-4923-A3C3-25F66DA260B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9731a9f3cebc07d9fc4aa92d6cd9d03b4d718bb","datavalue":{"value":{"text":"Near-colorings: non-colorable graphs and NP-completeness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2260631$3463F34A-A8FC-44C1-9A7E-21E1890095B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a40cfd1f9581b512cf8e020638ca116ebf53dcb9","datavalue":{"value":"1308.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$A14A9698-D4BA-4760-99E5-D175ED184CB4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e9731cfc25047c524a2a83588667b586efc613b","datavalue":{"value":{"entity-type":"item","numeric-id":274684,"id":"Q274684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$8A2DB6F9-7B00-4C34-A169-B38C13D45B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b3826c52088f4aa88f5af749aa0df3944c777e9","datavalue":{"value":{"entity-type":"item","numeric-id":244933,"id":"Q244933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$5FED6AB5-A97A-48D2-8244-8BCBD42D46B4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$47FE4F00-845B-46A2-919C-33FFA457AEF4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aaa340ae51925f6905d18399dfd97774b2ad90cc","datavalue":{"value":{"time":"+2015-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2260631$18C23796-7B52-4AAA-88FE-67896C8F0F2A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"49083f4eb30f89dea4c26b8e43cb597e31bc71a6","datavalue":{"value":"https://arxiv.org/abs/1306.0752","type":"string"},"datatype":"url"},"type":"statement","id":"Q2260631$22A8D343-EF8E-4B58-9A50-2D564AD73487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc49089b5fac6872152a21316269598d7cb998ab","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p57","type":"string"},"datatype":"url"},"type":"statement","id":"Q2260631$898C4DB8-2D82-43BE-85C4-B9DB17AF2929","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2feb2ff0fa32c4e7100127466a9eb8c0dfdf9678","datavalue":{"value":"Summary: A graph \\(G\\) is \\((d_1,\\dots,d_l)\\)-colorable if the vertex set of \\(G\\) can be partitioned into subsets \\(V_1,\\dots ,V_l\\) such that the graph \\(G[V_i]\\) induced by the vertices of \\(V_i\\) has maximum degree at most \\(d_i\\) for all \\(1 \\leq i \\leq l\\). In this paper, we focus on complexity aspects of such colorings when \\(l=2,3\\). More precisely, we prove that, for any fixed integers \\(k\\), \\(j\\), \\(g\\) with \\((k,j) \\neq (0,0)\\) and \\(g\\geq3\\), either every planar graph with girth at least \\(g\\) is \\((k,j)\\)-colorable or it is NP-complete to determine whether a planar graph with girth at least \\(g\\) is \\((k,j)\\)-colorable. Also, for any fixed integer \\(k\\), it is NP-complete to determine whether a planar graph that is either \\((0,0,0)\\)-colorable or non-\\((k,k,1)\\)-colorable is \\((0,0,0)\\)-colorable. Additionally, we exhibit non-\\((3,1)\\)-colorable planar graphs with girth 5 and non-\\((2,0)\\)-colorable planar graphs with girth 7.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260631$462EE998-5667-4D7C-93F1-8B09DC379DB9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$1947E053-8FF3-40C0-B2F3-47961DFC6EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$C4605825-16A0-41E4-8432-67EAA0863B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$E35B3684-34FE-40D2-8922-D3F798CD60FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$42B0147C-7659-4A34-9002-AE143E3C6EEB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1020116cde5b34f7e34d70b9dd84215482dda138","datavalue":{"value":"6413661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$7918AE6F-40B6-4D75-915D-B3B5631C27A1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260631$3C728FC0-E030-41A2-9854-A4649137CA8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b16134084bfb4d2d0e1bd9ff05e424149776914","datavalue":{"value":"improper coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260631$B292B088-37F6-445C-AF62-DD10D73D2E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260631$5BA4B28D-DC08-4B96-87D9-0E95A3D76A7E","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":"Q2260631$05199DF9-2753-4AAD-B1D6-A68537CC9243","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"86187cd049bd6565ddbc4e21f37dc55f378bee76","datavalue":{"value":{"entity-type":"item","numeric-id":1250223,"id":"Q1250223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$B2EE136A-34EB-47F2-9C04-D6977C393E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ce408a109a0f787c113b8dd93aa6eed7ab084c","datavalue":{"value":{"entity-type":"item","numeric-id":1250224,"id":"Q1250224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$CB0BD754-01E5-49D6-8D57-0630CC31D7F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97acbd5e3b1ffde45e9af83fb1a39ddf9c03df2e","datavalue":{"value":{"entity-type":"item","numeric-id":3115724,"id":"Q3115724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$3EBC7AA1-E358-4C6B-84C0-101FC89AE7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"739ac5be642f0cb6cba0194a627fb3cd8c6547b5","datavalue":{"value":{"entity-type":"item","numeric-id":3055928,"id":"Q3055928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$07B982DC-B593-443A-B6DE-9509D1D5150B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e21fdb5e782807e573fa97cacffafa912b7a8a20","datavalue":{"value":{"entity-type":"item","numeric-id":409448,"id":"Q409448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$C01760AC-E078-4A87-A18B-49A460CE95E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72897c88a4226029731bea2af8fd2fa709bbaff8","datavalue":{"value":{"entity-type":"item","numeric-id":411834,"id":"Q411834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$99A3C858-B061-4C68-BA97-036F254BB6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2759d0159ed2d156c3e47ae093d98824e41ee8e","datavalue":{"value":{"entity-type":"item","numeric-id":665888,"id":"Q665888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$BABDBEC2-62E7-4E6C-9A66-FC1BBA05B29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b771c04cedc66f488278e0bcf5f10790a814f2","datavalue":{"value":{"entity-type":"item","numeric-id":2434717,"id":"Q2434717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$A14CC0DC-0623-4DC2-BE5F-44CACAB27F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ef541518b27aaf0ba659700c2289eda0f52b392","datavalue":{"value":{"entity-type":"item","numeric-id":393935,"id":"Q393935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$2C75D201-F325-4A5F-889D-394B1ADD5D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77b39f4eae1816e03210090f9a802bf171d86d88","datavalue":{"value":{"entity-type":"item","numeric-id":2978189,"id":"Q2978189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$FC9B36B8-01CC-4EF1-85FF-8932801A7930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"908c64e882de0c6937e31f315702804b6e91ad96","datavalue":{"value":{"entity-type":"item","numeric-id":488297,"id":"Q488297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$FEEDE863-4108-41BD-8B54-A01081094455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eccf12a6ae2582ef4d7f460d18d2033f9a0e8c8f","datavalue":{"value":{"entity-type":"item","numeric-id":3728016,"id":"Q3728016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$DDB0A947-8397-4DFA-90CF-F867A5A502F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da8e270c7e7c46b5adbbdda7931650e17a4f0ec","datavalue":{"value":{"entity-type":"item","numeric-id":2874099,"id":"Q2874099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$AAB656CF-7490-4395-AEB7-62B451F88725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00244dff64a250ad217201f7377e62331a6f0c4","datavalue":{"value":{"entity-type":"item","numeric-id":4230860,"id":"Q4230860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$DC976605-0DD9-40BE-AF89-B4C9ACF4467C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7135fe3a9fe6aaa388a0857fd0be52835a2a62b","datavalue":{"value":{"entity-type":"item","numeric-id":4920652,"id":"Q4920652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$ADDDC4E8-B69A-4937-A8E3-439F5DE1CFB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f936b7b5e1f539097dfaa49a7930cad78a8de176","datavalue":{"value":{"entity-type":"item","numeric-id":4443116,"id":"Q4443116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$362DA62A-9314-430F-BBA9-FC5D0E65ADC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$5849A36D-6CE9-453F-BA08-348B5694A0B5","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":"Q2260631$C7018A6D-AE5A-4D08-A855-0EDB4E96F5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34bfe0e6bd8000585458313b42c3688bf056d88","datavalue":{"value":{"entity-type":"item","numeric-id":2481195,"id":"Q2481195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$B5F54662-6FF0-4E57-8161-45B52D252128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac21e64fcbc731b5be0a9a1fcc1867cb058fb137","datavalue":{"value":{"entity-type":"item","numeric-id":5486272,"id":"Q5486272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$C0521571-61B5-4A79-9A1F-20F46817598F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9a9714620f7be3c038bfbe634e16819139130a","datavalue":{"value":{"entity-type":"item","numeric-id":404440,"id":"Q404440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$F22C4E69-C5DE-4CBD-B549-89EDBFD75310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a00bc7a58e09cc04b187bbdfd4066a59ace071e8","datavalue":{"value":{"entity-type":"item","numeric-id":4256694,"id":"Q4256694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260631$FD338069-E7DE-41C3-91DC-23E3DB0ED621","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1fc8560992f0d79afc7973e8eb33b4b8da40bd6a","datavalue":{"value":"bafkreiafwov4fgyaytkfmtpl7ouqg5ybmlx7fj575mn5w3mngscbgq6yvm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260631$98A30443-03CA-4432-B9DD-E29D07B82DB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1de065992990e19194508a3d4b41d6ef8f1d19ad","datavalue":{"value":{"entity-type":"item","numeric-id":1679905,"id":"Q1679905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d64d9a7893df4026afbcadbe48db5577ca46e9","datavalue":{"value":{"amount":"+0.8204062581062317","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":"Q2260631$45C48DE7-FD6E-4C12-B2DA-0C61D7371ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e8c9f0569f87beb20b14b0962b623393b72f9ab","datavalue":{"value":{"entity-type":"item","numeric-id":1637126,"id":"Q1637126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fab6f471bfb7e897575bbd6ce721a163aedc1125","datavalue":{"value":{"amount":"+0.8044596910476685","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":"Q2260631$71C9D471-89D8-4167-B774-70AC2FB4B360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a58bfba75a742ac662eb99922cbe06aa02260ffa","datavalue":{"value":{"entity-type":"item","numeric-id":3424891,"id":"Q3424891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d0984b23c9390676f7ed6bb90cf937d1047874b","datavalue":{"value":{"amount":"+0.8016948103904724","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":"Q2260631$D9909938-3600-40AE-AEC1-3DF5D3563359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3b510cd888ac3dc8004121ba7d13f8ef77918e1","datavalue":{"value":{"entity-type":"item","numeric-id":2329168,"id":"Q2329168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e16e701909aa428d499d815473f9d32c36156ad","datavalue":{"value":{"amount":"+0.7965937256813049","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":"Q2260631$902DB57F-4C8F-454A-8DA4-00730F506D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cd69ba857c4bc69152a6116827262019ac11ed","datavalue":{"value":{"entity-type":"item","numeric-id":2324512,"id":"Q2324512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20ba9150259ef28c785fdf0902a790f0ce88b627","datavalue":{"value":{"amount":"+0.7914130687713623","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":"Q2260631$1F72E063-B42A-487A-979E-733746FD331A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2260631","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2260631"}}}}}