{"entities":{"Q528481":{"pageid":530248,"ns":120,"title":"Item:Q528481","lastrevid":52801751,"modified":"2026-01-23T13:08:37Z","type":"item","id":"Q528481","labels":{"en":{"language":"en","value":"A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6715033"}},"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":"Q528481$17AD002E-D083-4FFB-871C-7DAAFE4148FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb2d5833b148344f1e251ea25353b896eb60e87f","datavalue":{"value":{"text":"A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q528481$928EEF55-675C-4B64-A008-7DED6E3A3D6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"39ddedce7754c5c1f41ccffcdab6491ce72d9f8b","datavalue":{"value":"1369.68246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$AD9590D8-0BFC-48A8-ABD8-4EAE7B8B91CD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528481$9D1745C9-04FE-469B-B231-FD7979AA85B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"da189f927ef60f6fc1a9445574ffefbf706f10da","datavalue":{"value":{"time":"+2017-05-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q528481$2963D3D2-BE74-4999-979F-58506851F499","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$AA2A4809-C348-4F0A-8CF0-060DB20E4F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$A7279953-9454-41C9-937C-9AE7907DE000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$5B24F285-3F6B-4E27-921E-D123EAC3F58C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7121f628f9d20f83ee445a9ca701610aae3dbaa6","datavalue":{"value":"6715033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$353F952B-F94C-4988-9685-476F8166D339","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q528481$412CA047-C84E-4C49-87DA-22F99BFF9B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1520de8379415749656b1e95045c660d5b7f1330","datavalue":{"value":"fixed-parameter tractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q528481$BD58B58A-9B26-4952-81EA-0DD79F7E48A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c848be20a9df9788b716f450ec8f21487ece7c32","datavalue":{"value":{"entity-type":"item","numeric-id":1668077,"id":"Q1668077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528481$CFED01C2-BD1C-45A2-8141-A3A4F4E74FC0","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":"Q528481$6A1FC476-2AD5-455C-9080-AAC43B06E496","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c5b590559c441af1ea2ee24cd49bde1ff6c501b","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2017.02.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q528481$B56EA49A-A554-470E-BC91-58E2F5EB8AF3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4a9f0f9a57887900f9b8a51666b15e81eba363d5","datavalue":{"value":"W2588373402","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$C9CF6991-D89F-41A6-BBDC-0F7BD6A34506","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f492666460a4d0bf81e2d5a9ec14d5275ae9145","datavalue":{"value":{"entity-type":"item","numeric-id":730005,"id":"Q730005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528481$41A4CE2A-FF9E-4C89-A93D-730BF36F6E09","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":"Q528481$8F5AD8A5-DFEB-46DF-8136-DBF02B3B552F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ebbfed6cc9492b357ed7f3bf7eb049105a34988","datavalue":{"value":"10.1016/J.TCS.2017.02.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528481$8E457748-06C0-4E13-995A-E15C83D8871F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bad7008c67d1f330cab724d21e92887103ceec83","datavalue":{"value":{"entity-type":"item","numeric-id":730005,"id":"Q730005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aaf3b1485504fccb8167b8498d89312048ebcac","datavalue":{"value":{"amount":"+0.8954586386680603","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":"Q528481$DF27AFE3-021F-48E0-B65D-D7B5C61F143D","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":"bfc449806617ad45f22b6390bc64d947335df011","datavalue":{"value":{"amount":"+0.7944799065589905","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":"Q528481$EC2D99A1-7FCB-4448-8130-79AF75B6938E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0d005b192fadb46a27ecd247214c1c195acf695","datavalue":{"value":{"entity-type":"item","numeric-id":2422742,"id":"Q2422742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"023f4b831fb8bdc990ab2e1e1cdce97976f3d1db","datavalue":{"value":{"amount":"+0.7788968682289124","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":"Q528481$D1D2AA61-3002-4C55-9566-38EC2AD8BC4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7033d97d92185f53505832b6d8383be4176a484a","datavalue":{"value":{"entity-type":"item","numeric-id":3558598,"id":"Q3558598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfbec5b49d9d273513799b3a8f398e5c3e652711","datavalue":{"value":{"amount":"+0.7772396206855774","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":"Q528481$5C8B57D7-ECE2-494F-A985-FFB4CD094506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f58e2e6b5c6601f8ebe812445bb7fd973dbaef1","datavalue":{"value":{"entity-type":"item","numeric-id":4652867,"id":"Q4652867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e2515b07df9489bc94b265bf4c785260e8add49","datavalue":{"value":{"amount":"+0.7726799845695496","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":"Q528481$0ABBACCE-F60A-4851-87BA-407D5AF1E21D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:528481","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:528481"}}}}}