{"entities":{"Q1933643":{"pageid":1944385,"ns":120,"title":"Item:Q1933643","lastrevid":69099177,"modified":"2026-04-13T04:46:41Z","type":"item","id":"Q1933643","labels":{"en":{"language":"en","value":"Three complexity results on coloring \\(P_k\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6128660"}},"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":"Q1933643$168EFF98-AEC0-421F-A535-0C6529585ED6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"07393c8ef192fb5318960a9712ff7e9ab0b4eada","datavalue":{"value":{"text":"Three complexity results on coloring \\(P_k\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1933643$3C1A00E8-0697-4CF6-B8ED-E6BE1543046D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a44c2064781d7f4b03d32494c4f95a78603450d","datavalue":{"value":"1257.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$432376A8-6951-4E17-BFE2-7513E1C533D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a8874875f41e100f7dd0c90f8e9a202da131938","datavalue":{"value":{"entity-type":"item","numeric-id":259035,"id":"Q259035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1933643$B2EE01CD-65C1-4CFB-8262-00555587808D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c8bda24e5db7031b811824423dc274be5147149","datavalue":{"value":{"entity-type":"item","numeric-id":170462,"id":"Q170462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1933643$A27FAB45-D866-4378-923C-DE519928CD81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c15cd32c54abc58fde12b9b90b6f282b53cb3156","datavalue":{"value":{"entity-type":"item","numeric-id":339483,"id":"Q339483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1933643$C4E6E15F-9A59-4EC8-9B24-4AC5C9F46472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a4df628262abf79464ed4f15ac79f197844f8c4","datavalue":{"value":{"entity-type":"item","numeric-id":259036,"id":"Q259036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1933643$D9831B73-9B51-49AC-99F3-37A556E43B65","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1933643$B2B8A311-E467-4CC3-9823-149809B1D6D0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"97efcfeb60ae9286fe58dffb6ddf031782f90aea","datavalue":{"value":{"time":"+2013-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1933643$6EE308CA-0C45-4797-A409-DA63932D3BC3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$4F18C7C6-7750-4E12-9A0C-251A2834507F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$1EB6A71C-8E38-46F4-BD63-C88FF1F7F6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$B18577D8-D260-41AE-90ED-AB0F65B55CBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$B10B955E-5600-4803-8C03-2B20D8C2C682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$57364627-E5CD-44E8-94D3-C90662DCE38D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$357C3172-6EC3-4BFF-B1A9-8E2565545C20","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d87653ea7f99ae9ef0fb5e61c0fffaeb25642c02","datavalue":{"value":"6128660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$4B9FA564-420F-46D8-9C8E-D60643BEC966","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcabe08102492dc2cd54fa9819cb8eea09efdacc","datavalue":{"value":"dominating clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1933643$D740E6A9-F3CB-41E5-BFCD-EFC52400B71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1933643$28006BD8-23F2-4DE8-966A-28FCD5A20BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7b77d213f34227b1d7ee441c106cf7aa1b2428f","datavalue":{"value":"path free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1933643$672B5B9F-59D6-400D-B839-687CFB344AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db35356482fe68644ce3dd47f8632c04df7eed42","datavalue":{"value":"vertex colouring problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1933643$56989E0C-81A3-4A09-B52B-F3963BFFAC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"375d4e4974b8d8416474c562f59ac8951e9ee544","datavalue":{"value":"pre-colouring extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1933643$921D03C8-EDBD-464B-9D93-8D24014AEFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48e3b3f22ab69d6034250c9a42760908e5981ccd","datavalue":{"value":"polymial solvability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1933643$39731C1E-4415-4AAE-8E18-50B6D7DD96F2","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":"Q1933643$FD9EC591-B481-4719-B170-1F27D5314AFC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"385193e5aae822fbd10cc0be10f3d3ebff3bdf9c","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2011.12.008","type":"string"},"datatype":"url"},"type":"statement","id":"Q1933643$91C8BDB2-9BF4-4E28-9073-46757E561B8C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c63b9f3923bd2666db9a8dceb3ab278c5599df06","datavalue":{"value":"W2159829425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$9BF00893-C0FC-4132-AFC7-FFFF13158726","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b184f3198638f68e35f07e4d93d4ce523d0114a4","datavalue":{"value":"Q60488525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$0AA13057-D847-404C-ADA2-10374874C65B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"58a5f067b2622721474cdc32eb55942ba32980a4","datavalue":{"value":"10.1016/J.EJC.2011.12.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1933643$47F99177-D234-48EF-A810-D0BFDC023B77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"441e219b2eb150d707cfb55e453083e80070d90b","datavalue":{"value":{"entity-type":"item","numeric-id":3651537,"id":"Q3651537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40dbf6fd811e6f8313a949be08a80f9a09586d0b","datavalue":{"value":{"amount":"+0.9975990056991576","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":"Q1933643$CFE1B0EA-444C-48DC-BB69-9716F457567C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef4a5b069131ab4703bc08f14b0d64a80d6c079b","datavalue":{"value":{"entity-type":"item","numeric-id":2849942,"id":"Q2849942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afb08c0508180271450e5b473cd6b932f068767f","datavalue":{"value":{"amount":"+0.9161431193351746","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":"Q1933643$0A3AD390-9887-4FBA-B33D-BE96BED0894E","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":"afbefbfd9f1a798085f62fb115cefb232480c74f","datavalue":{"value":{"amount":"+0.9154369831085204","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":"Q1933643$405336C8-BA65-4B6D-BE1E-37B962C3B970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c59f2f669b65833bf5a4f8f3ca180543e3b0aa9f","datavalue":{"value":{"entity-type":"item","numeric-id":499486,"id":"Q499486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40d0ce680043fee265288a2bcd8793e83f3a19cd","datavalue":{"value":{"amount":"+0.906300127506256","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":"Q1933643$9995536C-2509-44B1-AF58-1B9963748B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5873cd02288c7bc556680231a71532e43c6582b0","datavalue":{"value":{"entity-type":"item","numeric-id":764301,"id":"Q764301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e47a776f0a1bc46a03f74971e41cbbaabfa9eb92","datavalue":{"value":{"amount":"+0.8915613889694214","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":"Q1933643$ECA97538-E2A7-465C-B6E4-088766AC89D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Three complexity results on coloring \\(P k\\)-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Three_complexity_results_on_coloring_%5C(P_k%5C)-free_graphs"}}}}}