{"entities":{"Q3029023":{"pageid":3039739,"ns":120,"title":"Item:Q3029023","lastrevid":49092748,"modified":"2026-01-06T14:17:20Z","type":"item","id":"Q3029023","labels":{"en":{"language":"en","value":"Graph Minimal Uncolorability is ${\\text{D}}^{\\text{p}} $-Complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016922"}},"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":"Q3029023$73F954A9-215B-47C1-BE6C-D2E8D65920CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eb86dcd8a8cb986de6825f4ed4f96bea257f8640","datavalue":{"value":{"text":"Graph Minimal Uncolorability is ${\\text{D}}^{\\text{p}} $-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3029023$741A0345-FF52-4894-832A-3AE3DD1336A0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"757d9037243a138072d6dd49305d684617c4d405","datavalue":{"value":"0626.05017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$C566D931-B160-4E30-8C57-CBF709822814","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24f56bfd93c57b859615abe41fe3531157131ed0","datavalue":{"value":"10.1137/0216022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$8756A33A-DBBB-435F-B94E-D6A133671E78","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"153f087410d6445d3ecf9b2f61b070cffa67488f","datavalue":{"value":{"entity-type":"item","numeric-id":269464,"id":"Q269464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3029023$27B72344-A404-41CA-B7B9-E0AF0A123C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97f54a35ab1ebcb4e4c3fe284662b9126a1ad18e","datavalue":{"value":{"entity-type":"item","numeric-id":3029022,"id":"Q3029022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3029023$B8EF63D7-94FD-489F-B9D5-9C59741621D2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3029023$8B12F420-0B2E-46CE-8E04-365A4A6539A9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3029023$E8F07DD7-8CD8-4B13-A432-34A0E9317FA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$AD5CAD15-907E-4CEA-B6F2-0EB3E77125F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$6E169F91-15AA-4E1E-8498-F3A7B3839458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$D908D682-B29C-4D42-A7FA-5EA19527D2CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$C12F88C0-EFCF-4B18-B304-310C5C6E72FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"834edb7c29e50801a927a3e4fc5de7a1f9fee147","datavalue":{"value":"4016922","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$F32DB503-F876-4885-BB71-782752ED6FAF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3029023$CECCD078-FE03-4B30-8D6D-87D10716BDE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edd452f07ff284953f3a8a7af6f49f724d3f8826","datavalue":{"value":"\\(D^ P\\)-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3029023$D0D59176-634D-4A8C-B120-23B3E7A5B4D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q3029023$5C962C2A-D99E-4899-8FEE-FEF57DE2214D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"901ad854164d9d015e5f2725e169de1aff7d2840","datavalue":{"value":"planar graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q3029023$681B6F61-5844-4F5D-8AAF-C1F0A04878AC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bb3aaf4fbae4ee628251163ff0a0da5157ade074","datavalue":{"value":"Q59795792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$7458DDAF-0BB7-4D8E-9B24-A47032F5C3BC","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":"Q3029023$A5D45562-FDDE-4045-ABBC-8B1754434B1B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c43070205d1efde6b65edc17a9ed2974e70257b","datavalue":{"value":"https://doi.org/10.1137/0216022","type":"string"},"datatype":"url"},"type":"statement","id":"Q3029023$C1BC34F3-EE83-4D63-B39A-FF4FDABA402B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"60b2f736d5557416705c3e84db2dffe02c7f58fa","datavalue":{"value":"W1806792047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$FBBCDB33-A9A2-4B34-A7DE-A51D134E80F0","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"dfaa90fbf4e47a640d4c26bba910701ff647d65d","datavalue":{"value":"journals/siamcomp/CaiM87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3029023$65C304FB-6EA9-447A-BD76-16411799580B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fa0bf508bd15db5717af9c78fd2492243673cca","datavalue":{"value":{"entity-type":"item","numeric-id":3766875,"id":"Q3766875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e70a36436112db5bc31f2a2a5cdef0cf2f8095f2","datavalue":{"value":{"amount":"+0.9553608298301696","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":"Q3029023$6ACBAA25-015D-478B-946A-F5860FE5382F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a00284b2fa5568a414a9146567fac23f50d5d051","datavalue":{"value":{"entity-type":"item","numeric-id":3347294,"id":"Q3347294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b45b28a7ac47b67ecbe10f71454c1cbbc5089b48","datavalue":{"value":{"amount":"+0.8363487720489502","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":"Q3029023$CEEFB3B9-D691-40D9-A1AA-EBBB56F4C340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89dacd94fc24813bd4cf458d3d0cd2cdc474ef5c","datavalue":{"value":{"entity-type":"item","numeric-id":1356685,"id":"Q1356685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe0320eddcd3f3d5f39f1f24e5355d7bd7415f09","datavalue":{"value":{"amount":"+0.7900474667549133","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":"Q3029023$50B5B826-7979-4E60-B4F0-09AF5018B37D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09ba7f1926c8987d3181b45ed3709dbc321b81ff","datavalue":{"value":{"entity-type":"item","numeric-id":596079,"id":"Q596079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72b9e7150c70223925bd60b5021ef7579b534917","datavalue":{"value":{"amount":"+0.7832327485084534","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":"Q3029023$92450812-939E-40C5-A45B-753D4D164850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26984029d1291a608e525e2600c141c74c83ca0b","datavalue":{"value":{"entity-type":"item","numeric-id":3182925,"id":"Q3182925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad09eaae8f19dcb150054e193a54cacf7aa437e7","datavalue":{"value":{"amount":"+0.7629660964012146","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":"Q3029023$3824B5D0-CF32-467D-8514-CBDBF3F9E408","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3029023","badges":[]}}}}}