{"entities":{"Q848637":{"pageid":850485,"ns":120,"title":"Item:Q848637","lastrevid":64827930,"modified":"2026-04-11T22:30:05Z","type":"item","id":"Q848637","labels":{"en":{"language":"en","value":"Deciding \\(k\\)-colorability of \\(P_5\\)-free graphs in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5677428"}},"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":"Q848637$3C2D7ACB-B534-4502-8338-53B77F749B08","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ced450e098a58eeb0ff11bf8f0f24fe15e11e072","datavalue":{"value":{"text":"Deciding \\(k\\)-colorability of \\(P_5\\)-free graphs in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q848637$56895AFB-AA02-48CD-B798-97333E9B3ACE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba3a22b0754c0b26631ba479fd7b4ca7a9db802b","datavalue":{"value":"1222.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$6E346C95-93AE-4CBB-92E6-F1258CF3944F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7598b946dc98bf1d17807d2ef3a244f2419361f8","datavalue":{"value":{"entity-type":"item","numeric-id":234396,"id":"Q234396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$78883836-152B-4757-A988-7C6DA9E6B728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31cef5836d6ac4ca81e8a47258272f91a1788c44","datavalue":{"value":{"entity-type":"item","numeric-id":299049,"id":"Q299049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$256D36BF-DC02-40BA-89EC-28DB607F9B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d678b728b8c92d8051702e4ebf54599872f73e18","datavalue":{"value":{"entity-type":"item","numeric-id":848636,"id":"Q848636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$9CDB20BB-8705-4651-A26C-2139493D14B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1aee8b2e156a4dc08f28586a944ab8da5a4e706d","datavalue":{"value":{"entity-type":"item","numeric-id":191506,"id":"Q191506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$0E528F97-B01E-43D3-A0FB-349CA352F5A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9924970a3259a1323042c8227a65163844bb317","datavalue":{"value":{"entity-type":"item","numeric-id":317397,"id":"Q317397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$4C6F0D9F-9D4B-49EE-AD2F-1F3802B5192E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$620F1174-E6B2-45F2-91B7-06443915AA37","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"355ea7e9fd14aaadfb5a5632e845e3bf053937d3","datavalue":{"value":{"time":"+2010-03-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q848637$CF403530-1AAA-4BEC-B812-7320ECE2CEE2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$A89AA690-8001-494A-9FEB-F4D047E59C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$97C49F5B-D70D-4BDF-9002-4F613F564502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$2FA8AAED-1834-4F76-A96D-FC8C00C5E58B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6f48c8d18337aa467a843bb358ec31b787e3f0e2","datavalue":{"value":"5677428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$14F52D31-0404-4B23-9882-8B4D68C50458","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q848637$543A204D-67B8-4CA4-85AC-744577AB4523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcabe08102492dc2cd54fa9819cb8eea09efdacc","datavalue":{"value":"dominating clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q848637$D0338C07-96C4-4D93-A1B3-562EDC0CF110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q848637$48F716EE-A8C6-4484-8479-699BF9432319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d461ceeb0a5404ac1aa2740db0be3b8188404ff1","datavalue":{"value":"\\(P_5\\)-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q848637$C712D448-0B5E-4B8C-B38E-A54E3C2B0BA7","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":"Q848637$3810E60D-5B17-4EDD-8F74-FE9D0E386D96","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cdc986467b77f0f9a03a3e30ef622bdecd16cb8c","datavalue":{"value":"https://doi.org/10.1007/s00453-008-9197-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q848637$8D3D3C88-DAD6-4E8F-A600-85E2AD8A01A8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c4773d5c22657d597ea72d5bbf960b307d2a99df","datavalue":{"value":"W2282776087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$37432010-2DF5-4A14-BAEA-B3E2DD003092","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b69b5b03a7ed1f39c895674d8c97ff4c5a0355f","datavalue":{"value":{"entity-type":"item","numeric-id":1176051,"id":"Q1176051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$9C28B2E4-2D1A-4250-A059-C96657F96C76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480ac560f713e57a5ee8cd072f59d2635f9c43d4","datavalue":{"value":{"entity-type":"item","numeric-id":915378,"id":"Q915378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$613D0B3A-1A99-485A-9DC4-B0A5C8B639BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$F32CB012-7E7E-4693-8519-2FA5440927E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e1c3bb11a57c04f9f5dd769e29680f16e9d58c","datavalue":{"value":{"entity-type":"item","numeric-id":4809665,"id":"Q4809665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$D7A537D5-4D7D-45B0-83C9-2C66FB2F66BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"319fdaa27484a2ebcce1969d012e31307e954320","datavalue":{"value":{"entity-type":"item","numeric-id":5663894,"id":"Q5663894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$C4AE95B5-6506-4A1C-80A9-ED12F78C80BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$D4383035-A6D1-4127-91C5-89DF73D6810A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad785b95c6d6543e7b216b915da985a62d3db5f7","datavalue":{"value":{"entity-type":"item","numeric-id":1382285,"id":"Q1382285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$4C8228AF-E524-42AA-B923-A0CF333B58CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$D4AE6AFE-6C6C-4580-826D-669C0286A6FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed7197995b093007527a5d546d60b05148a6d9e","datavalue":{"value":{"entity-type":"item","numeric-id":1822967,"id":"Q1822967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$26F33A2E-3633-4052-BEB5-C9ACE6534670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$71FA17B1-CF09-45E6-BB2B-247AA49D07C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4654aae8b18d38dae6f3ee82111d1335fc96fe89","datavalue":{"value":{"entity-type":"item","numeric-id":5932643,"id":"Q5932643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$A85C3445-3BC1-450A-BFFC-A1CB0B3304DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85c10db552a82a79e3dd01502bb63100f67a8a03","datavalue":{"value":{"entity-type":"item","numeric-id":3353058,"id":"Q3353058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$A8AB9B9D-BB55-47B9-82C4-BED842D946F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ecdad41b5a7ad19af25d12395ebbff6dd994fd","datavalue":{"value":{"entity-type":"item","numeric-id":4448764,"id":"Q4448764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$35575B56-0010-40EA-9B26-51913A0E41F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ce5569c41d29c6a54f9ded29b6ab521486ccdc5","datavalue":{"value":{"entity-type":"item","numeric-id":2465649,"id":"Q2465649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$2E17E44E-B29E-4246-94C6-F2A83CA3B0D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fec6d5d27c48b92a86d66707db8bd5dd67fb137","datavalue":{"value":{"entity-type":"item","numeric-id":1356685,"id":"Q1356685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$FA9FD1EB-699F-45FB-B669-D5DAF68E7967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"961551c5665512b67a21d966b3640e6a34d12524","datavalue":{"value":{"entity-type":"item","numeric-id":1889838,"id":"Q1889838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$85D3F14A-ECD8-40D2-95FF-A91007E42657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b97ec674c9801d3e945638d7eae4a8579650e83","datavalue":{"value":{"entity-type":"item","numeric-id":1427186,"id":"Q1427186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$ED1B56BE-447F-41BA-8F19-D2913FAE97CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51f56e9a479daaafcf6f38f3d85e504a101fb504","datavalue":{"value":{"entity-type":"item","numeric-id":1613477,"id":"Q1613477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$72529684-D137-4C87-A0C4-43A561A15659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be2a01198b1b63afd375056c2a1eff2d080abd2d","datavalue":{"value":{"entity-type":"item","numeric-id":2770587,"id":"Q2770587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848637$3F695A68-768A-4A39-B356-73650B72A321","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b5b56424b82bba8b1dbf4c52b40529ace671e1c","datavalue":{"value":"10.1007/S00453-008-9197-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848637$5DE59909-A905-40BE-A375-2B6D600404B8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17ac0f2c2f0c68dd9a356261472ca256ff3c8195","datavalue":{"value":{"entity-type":"item","numeric-id":3599143,"id":"Q3599143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af0c17c3d911136c4286b56a25b90547e5f757bb","datavalue":{"value":{"amount":"+0.8927943110466003","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":"Q848637$A9B76668-9FD8-44A6-9B7C-4A4CB1E9BA26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2380bd15ee6a039b8b33f282c85bdd39c9abb7e","datavalue":{"value":{"entity-type":"item","numeric-id":505438,"id":"Q505438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f41768a59c41eb1e446e6a70215e2ee4a935c3cf","datavalue":{"value":{"amount":"+0.8773960471153259","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":"Q848637$47B9825F-71C3-464E-8C31-C1648EF77456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dff66f421d9279a146f3853cd45730ed39779be","datavalue":{"value":{"entity-type":"item","numeric-id":2770587,"id":"Q2770587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"881fd82cca3712a667cf1da198a7d6d82a9e927f","datavalue":{"value":{"amount":"+0.8771463632583618","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":"Q848637$33724601-EA0D-4035-AA64-987C4E73A460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09b1fe45b411d07b425b1f0a42aaf4e9c4cffe43","datavalue":{"value":{"entity-type":"item","numeric-id":3057613,"id":"Q3057613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15b3169e13d2ad09f860dd4acf69eda2c77f3f5b","datavalue":{"value":{"amount":"+0.8697841167449951","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":"Q848637$C4DC7377-A1F8-4439-B013-235A7AAD382B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f6af490d6d839b0229bfcdb1c310527d76b0325","datavalue":{"value":{"entity-type":"item","numeric-id":1759872,"id":"Q1759872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e947b9fda147eaf1167f9ca13db363cf286445","datavalue":{"value":{"amount":"+0.8640203475952148","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":"Q848637$F5B203BD-95C9-4D16-B117-9FAB28F6B11B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding \\(k\\)-colorability of \\(P 5\\)-free graphs in polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_%5C(k%5C)-colorability_of_%5C(P_5%5C)-free_graphs_in_polynomial_time"}}}}}