{"entities":{"Q602756":{"pageid":604532,"ns":120,"title":"Item:Q602756","lastrevid":63062409,"modified":"2026-04-11T10:16:23Z","type":"item","id":"Q602756","labels":{"en":{"language":"en","value":"\\(k-L(2,1)\\)-labelling for planar graphs is NP-complete for \\(k\\geq 4\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5810808"}},"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":"Q602756$D8D813D4-E950-41D8-BE22-E6C9E2FD056B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9a3521aea5c2b51e655e2e21e45559bb06dbe532","datavalue":{"value":{"text":"\\(k-L(2,1)\\)-labelling for planar graphs is NP-complete for \\(k\\geq 4\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q602756$97366F9C-2C74-4352-A3B7-793A930547A2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"635c9b9f6cf3dc04291337e9422383fa222c6d1a","datavalue":{"value":"1209.05211","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602756$36588BF4-7AFD-45E5-8564-6860AA409439","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":"Q602756$D3672963-39A3-46BA-9C70-FE8EB0457BD0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e207171999d8bccd08779f13059dd3836085b46a","datavalue":{"value":{"time":"+2010-11-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":"Q602756$4629178C-BD31-4E61-8C63-D6FBC5CD6637","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f0acb8a4557606f04d294627bd8e6c6bb1f788c3","datavalue":{"value":"https://arxiv.org/abs/0909.2613","type":"string"},"datatype":"url"},"type":"statement","id":"Q602756$7BEE01BB-C0E7-4116-8ECF-B625FEB7C26C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602756$D3120219-0CE8-4728-8316-7789F879A91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602756$1A405EDB-BB92-42DB-AB19-1C85859D6B0C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"59742256193e495c68659c4d9fc06b1dd58ac5c9","datavalue":{"value":"5810808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602756$16F042BD-788E-4672-931E-C4FC34AC5C5C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"388326b981a7b744b7eb7ed8002667e59c696803","datavalue":{"value":"frequency assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q602756$0C39C29E-6A11-426E-8E52-A0DBED64562C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b455b45a24049ad9f1c8c1714bede3cd632c260a","datavalue":{"value":"\\(L(2, 1)\\)-labelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q602756$2953C037-78CC-4C0F-8641-B0292BA9A1EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q602756$3B60444C-F59F-4506-A8FF-F720418D0AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q602756$224FACF3-0B5B-45C3-B8E9-4CF20B2E0772","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83381e91dfe6a29bb0e52422ab92f926439f941d","datavalue":{"value":{"entity-type":"item","numeric-id":412350,"id":"Q412350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$A93870F3-66B4-466B-976F-4AFB9EB24287","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":"Q602756$FC0B3E6A-455D-47D8-9C09-2AF56BF468AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf5a0e86ee5fc1c6662191d40866b670f7742aee","datavalue":{"value":{"entity-type":"item","numeric-id":412351,"id":"Q412351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$9B4F012B-F8B6-456F-B6AE-2078F54B6C85","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":"Q602756$8EE64425-4517-4F0B-A297-5BCA214CD25C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3beeb349846f75980b0e4f414fdc6c8a09d337ad","datavalue":{"value":"W2043130082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602756$D5AAF950-C1C3-4623-9ABE-1520B371BB9A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0b978a3fde300752498655753f424af3625b14c","datavalue":{"value":{"entity-type":"item","numeric-id":2461777,"id":"Q2461777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$5D59CFB4-13E6-4E9E-8B62-6AF1E9F086BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59bacccfe65625085ab33c637bbda9c5b80666c7","datavalue":{"value":{"entity-type":"item","numeric-id":4470433,"id":"Q4470433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$E9FADEA1-4D29-4860-B876-C9E2BF8C3A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38cf9d079bd5fe64fef30b4581e169f5c5fc90cd","datavalue":{"value":{"entity-type":"item","numeric-id":1881282,"id":"Q1881282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$FEE95304-C616-4101-9B32-7BD75D26A51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a026cd0f4b7a301bb63b3a31e47f3cb40412d167","datavalue":{"value":{"entity-type":"item","numeric-id":4881295,"id":"Q4881295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$6D232927-766E-4B4D-A485-CC68063C75D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a990f583410535f69afc17385c6e5faa94f1593","datavalue":{"value":{"entity-type":"item","numeric-id":5716789,"id":"Q5716789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$6386974F-0132-4990-92B2-D7C9CD3B447F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b1b809f78fd9ef5e4bbdc205f01af098a7e2a2","datavalue":{"value":{"entity-type":"item","numeric-id":5948961,"id":"Q5948961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$72807C33-8B25-4144-8FDA-6C95F4B6E388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f7db6e80f8fc06453e26d8fedfb9818a0f28bfb","datavalue":{"value":{"entity-type":"item","numeric-id":4536372,"id":"Q4536372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$E3FFAD4F-72D7-4D7B-92F6-926F11D32DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8b22c65e9be5a796435b38c6cc58e5dcd1d3b6e","datavalue":{"value":{"entity-type":"item","numeric-id":2566036,"id":"Q2566036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$3CB86B45-EEDC-4243-BFC8-8A384303ED1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a415e76a6c4dfffab8c5043c692bae1e05da99b","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$B657A5A4-222F-4C17-A19A-9AF2B9774716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5e30d84b1087316bb3ae11884e4d89dd01f4c59","datavalue":{"value":{"entity-type":"item","numeric-id":3639233,"id":"Q3639233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$1E4A85ED-4888-4F9B-B5DB-6E18445EBD38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5edcfe97bd0789e66ea3303029b2acaa19a2b078","datavalue":{"value":{"entity-type":"item","numeric-id":837161,"id":"Q837161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$4400C0F4-BD85-4317-986E-73E9D38234CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a47755a3f68d46fd9769f68d415454c70926e0a","datavalue":{"value":{"entity-type":"item","numeric-id":3503513,"id":"Q3503513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$9D5DB598-0723-4987-A56E-F1F0863520E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d845eb2f01634e88fd96be629d241a787d691fb4","datavalue":{"value":{"entity-type":"item","numeric-id":3579493,"id":"Q3579493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$E76B2ACE-000D-4013-A764-1F9598DFC251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c5161e57cb21a6581530b516a6d9969157e39e0","datavalue":{"value":{"entity-type":"item","numeric-id":967327,"id":"Q967327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$92E9C89D-1DEA-4528-A010-5345FE4A334B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2dcd19a03014335d79842ee4ced55daecaa909","datavalue":{"value":{"entity-type":"item","numeric-id":4797924,"id":"Q4797924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$BC637308-03FA-4DF6-A275-8D4637E75E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$E9BDDE06-3A67-4578-B82E-6ED5E0E0C3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2ad854e4145ad8fc80246024186064227c61b4e","datavalue":{"value":{"entity-type":"item","numeric-id":2497501,"id":"Q2497501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q602756$BFAA893B-0CCD-4E40-A760-4B22E1CE880A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67a5fc078770894741a3b2631ff78dea700f74fb","datavalue":{"value":"10.1016/J.DAM.2010.06.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q602756$8B3BD150-9654-4458-8042-C23F11F878C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d16d7d1a51a3ba02663dec07b9c76d7f2c282904","datavalue":{"value":{"entity-type":"item","numeric-id":1025950,"id":"Q1025950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9551c41892de39eed35cb62b28506eafeff12c7a","datavalue":{"value":{"amount":"+0.8564746975898743","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":"Q602756$03BD5A6E-4E0E-454C-8CA8-2845FA889813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f510afab32129c5327a240256df88c0c060410e9","datavalue":{"value":{"entity-type":"item","numeric-id":5395075,"id":"Q5395075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"563f1408870d0c98910f515d71d68cea5c0947d3","datavalue":{"value":{"amount":"+0.8525314927101135","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":"Q602756$C620CF17-802D-4D36-A2B9-5B7AB09DCD5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9c14ac53b28bf815c8290d947bdfe951cdfc741","datavalue":{"value":{"entity-type":"item","numeric-id":3569077,"id":"Q3569077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56c0965bf1e3041daaf345fb52f247567545d587","datavalue":{"value":{"amount":"+0.8411307334899902","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":"Q602756$32E475F8-4631-499A-A469-C616C4933331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fe7e30c6817a23912ab35586ef98328221e055f","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"777735209da55de3875c86f90f546ae7012138db","datavalue":{"value":{"amount":"+0.815994918346405","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":"Q602756$EBBD792C-FFA3-4CBC-AEBD-CEE096008CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bab2e131df22722908ec75f42a6ea7ea17c73661","datavalue":{"value":{"entity-type":"item","numeric-id":3525597,"id":"Q3525597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20fb0df184d86871db3f0dc172c8f8245eb822f8","datavalue":{"value":{"amount":"+0.8141158819198608","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":"Q602756$8594CB1F-9D75-4D86-80BB-0F794BF0D062","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(k-L(2,1)\\)-labelling for planar graphs is NP-complete for \\(k\\geq 4\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(k-L(2,1)%5C)-labelling_for_planar_graphs_is_NP-complete_for_%5C(k%5Cgeq_4%5C)"}}}}}