{"entities":{"Q2404616":{"pageid":2415359,"ns":120,"title":"Item:Q2404616","lastrevid":72705714,"modified":"2026-04-14T06:41:30Z","type":"item","id":"Q2404616","labels":{"en":{"language":"en","value":"2-subcoloring is NP-complete for planar comparability graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6776062"}},"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":"Q2404616$7842A1B1-6B3B-4F51-8EEE-B1463F904C21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0612801393b120c8c9fa217069a6e81d871b249","datavalue":{"value":{"text":"2-subcoloring is NP-complete for planar comparability graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2404616$9468CC7A-8D44-4A86-A1AC-2BA940F44972","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d32d20ff90cb04820a9578be30482b27b9efe7c","datavalue":{"value":"1420.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$9619BE6D-515B-40EE-98C6-DA326C4D4BE7","rank":"normal"}],"P16":[{"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":"Q2404616$A4783232-C47C-4142-AD2C-9AF461102597","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404616$FA374317-A461-495A-A0FE-D52B39E3D0D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c21d4747e37ac8a83681ed541df851bfe5d23ff","datavalue":{"value":{"time":"+2017-09-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2404616$8433B6AF-6529-431B-9D6A-DDA49640B1AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4e9242d5ab8b4d21fe51adbd09fc5946a785379a","datavalue":{"value":"https://arxiv.org/abs/1702.01283","type":"string"},"datatype":"url"},"type":"statement","id":"Q2404616$EF2D6E7E-126B-4E72-A4E1-D5D70DEEF9B1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$47CAB0DE-1FAA-4D0C-9594-9412C95A86DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$73D12F98-F904-49EF-84EA-36D80779FC06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$1A78CB51-E8F6-4A7B-B65E-2EDE111A502D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae943efc66cc45fa46befffb47bd78b4c33c85f7","datavalue":{"value":"6776062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$77F42A2D-082F-473B-B9D2-557B512C6B8C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404616$0A7B8618-8A6B-425F-8828-29F44EFD40BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404616$AAC8054F-8265-4472-A2D9-53E7AE3E8682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404616$8DD2D540-F6A6-4F7C-84B3-7D52F761D6C0","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":"Q2404616$FE81C2D8-C0F0-431D-A7B1-034D39AB4599","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb8f7cdf40010431381770a364d72489ff66beff","datavalue":{"value":"W2593969461","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$D3D7E179-B747-444D-975C-5A6DAF071026","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"61319034919649333c50fa3438acc6711fe4034e","datavalue":{"value":"Q56428507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$E3E1E702-44AD-45A5-AE9B-FEE824CC24B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f0efa964a7a3c5381f9e78744ec00ab73a53184","datavalue":{"value":{"entity-type":"item","numeric-id":424720,"id":"Q424720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404616$ECADED31-39BA-4EDC-A894-ACB061A61333","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":"Q2404616$3BCFAF81-EBF8-496E-A249-7A355151D8E6","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":"Q2404616$ABE23D9B-2A64-4BE5-8E7A-1EB8A189D9D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00f8204108984a736d2c274f4eb22393a03bba1c","datavalue":{"value":{"entity-type":"item","numeric-id":1025569,"id":"Q1025569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404616$AD8AA539-E87A-413C-8CD2-9D5FDE2DDD00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404616$2270B97E-364B-40C8-8A04-B87CFAD8DA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c1e22be0f2e191ce2eafd588eef7934e0fdfea7","datavalue":{"value":{"entity-type":"item","numeric-id":2260631,"id":"Q2260631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404616$CC06A322-1E5E-4574-9E90-FE861D8A6B6E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b577f59b0e0fbd0ee1be92393627eeb4d27c3791","datavalue":{"value":"10.1016/J.IPL.2017.08.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404616$C90ADD3A-01E3-4804-AE14-A7622D6D97AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"224fc1e854280094014365736f4834209a69fce3","datavalue":{"value":{"entity-type":"item","numeric-id":4448755,"id":"Q4448755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"806ae5d5be3b612b658f1aaab02778222c381b03","datavalue":{"value":{"amount":"+0.8799014687538147","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":"Q2404616$26E4279B-081A-4A92-9436-F4B9E043E34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f266ed8e741b2bda58404cc299a84bd2e62f934","datavalue":{"value":{"entity-type":"item","numeric-id":4414486,"id":"Q4414486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"932015940fb238d0a7572e25b2f921459897c03c","datavalue":{"value":{"amount":"+0.8757144808769226","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":"Q2404616$6CFC3F9C-4204-4E9C-A7D6-C097C2C84181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5949e69fe781f2897b9ca406e18cb21cfc853ede","datavalue":{"value":{"entity-type":"item","numeric-id":1603517,"id":"Q1603517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"932015940fb238d0a7572e25b2f921459897c03c","datavalue":{"value":{"amount":"+0.8757144808769226","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":"Q2404616$DA80517A-3B42-4903-A484-2BB1E9557E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fa7598e7b2aae9473bb3b8c0ee5c5b3688d6902","datavalue":{"value":{"entity-type":"item","numeric-id":424720,"id":"Q424720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47d5bb8c25ff6eb85d97c06331431a4762118b0e","datavalue":{"value":{"amount":"+0.8750104904174805","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":"Q2404616$3CEF5BF8-5F9D-44B0-9C43-D84164462D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a24b9c34520cf046605ff2ea37fa0af8a628fe05","datavalue":{"value":{"entity-type":"item","numeric-id":4443116,"id":"Q4443116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2d245d39a8edbc079c4507518390a154ae5da55","datavalue":{"value":{"amount":"+0.8749856352806091","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":"Q2404616$E11A6270-641A-44D3-ACC6-4B6E02FF96EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"2-subcoloring is NP-complete for planar comparability graphs","badges":[]}}}}}