{"entities":{"Q1883661":{"pageid":1894403,"ns":120,"title":"Item:Q1883661","lastrevid":69383793,"modified":"2026-04-13T06:38:21Z","type":"item","id":"Q1883661","labels":{"en":{"language":"en","value":"Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2107488"}},"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":"Q1883661$BF7A66BC-452E-4EAB-A9F7-6DCB04705AE7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e536e31d346a5d6e925468a7337d42d10a37cc76","datavalue":{"value":{"text":"Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1883661$AB447DBD-56AF-40CF-9175-1C5FAA0AAE52","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6e415051ea37ce1f6db4d3984ee7824f66f1c87c","datavalue":{"value":"1053.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1883661$32CF9584-908E-451F-BA6E-42560D81B4B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1eabfed33776a4058364f5e437a36b01c9e455e9","datavalue":{"value":{"entity-type":"item","numeric-id":878621,"id":"Q878621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1883661$8AFB31F5-5201-4018-BC5E-B286E2A063CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1883661$503C903E-79D3-4E97-B443-D7E42489D2CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e4f786a34efe92a3c62c92ebfcca3c44a498bf2f","datavalue":{"value":{"time":"+2004-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1883661$9FEB70A9-A940-4AD5-825E-3B540F022885","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"40a6b99f2002a3a3d01451f2a595d01c99f1e4b3","datavalue":{"value":"https://arxiv.org/abs/math/0306158","type":"string"},"datatype":"url"},"type":"statement","id":"Q1883661$BF031E2F-86C9-460F-A05F-882BA69AE483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"82ef838fdd1c0f675be5d7d99a7aa40eb67ba0b3","datavalue":{"value":"https://eudml.org/doc/124013","type":"string"},"datatype":"url"},"type":"statement","id":"Q1883661$F7023322-EB6D-4874-9675-D9117BEE3583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"543b08ce9773f524e01ba1ec910558e531bb2ed2","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_11/Abstracts/v11i1r46.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1883661$CAB55474-A0DE-4247-8A85-A5CFC58F8AA0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c33498042315da88b625bd65c300cfe703e1c93d","datavalue":{"value":"Summary: Can the vertices of an arbitrary graph \\(G\\) be partitioned into \\(A\\cup B\\), so that \\(G[A]\\) is a line-graph and \\(G[B]\\) is a forest? Can \\(G\\) be partitioned into a planar graph and a perfect graph? The NP-copmleteness of these problems are special cases of our result: if \\({\\mathcal P}\\) and \\({\\mathcal Q}\\) are additive induced-hereditary graph properties, then \\(({\\mathcal P},{\\mathcal Q})\\)-colouring is NP-hard, with the sole exception of graph 2-colouring (the case where both \\({\\mathcal P}\\) and \\({\\mathcal Q}\\) are the set \\({\\mathcal O}\\) of finite edgeless graphs). Moreover, \\(({\\mathcal P},{\\mathcal Q})\\)-colouring is NP-complete if and only if \\({\\mathcal P}\\)- and \\({\\mathcal Q}\\)-recognition are both in NP. This completes the proof of a conjecture of \\textit{J. Kratochv\u00edl} and \\textit{I. Schiermeyer} [Discuss. Math., Graph Theory 17, 253--258 (1997; Zbl 0904.05074)], various authors having already settled many subcases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1883661$80D6C525-E493-4C24-9B7A-DA2E3726FA50","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1883661$93033965-0BB2-40D5-9828-AD66B0B2B2AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1883661$1908D4C5-17DC-4A41-899D-678DB26337B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1883661$B39B06F8-E17B-45E9-AA91-8E4AB4D4B43E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"afc90b86b0dd2e581cbf9f91726a631ebfea347d","datavalue":{"value":"2107488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1883661$2B49C97D-7A63-48F7-BDB0-9811515068A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3da21ca1a98193e8984bf1ee1c4e9286099f1f","datavalue":{"value":"vertex-partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1883661$DB65ACC4-CC74-4AAA-9F8A-26DA7107A737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"842c70fb0eec2bcf6f5aa032457cab3502d126ca","datavalue":{"value":"line-graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1883661$1EC36176-D23B-421D-8785-EC91A6CFEB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1883661$BFF07E1E-28B1-4E9B-BDE5-B53FC6CAC4CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1883661$CC9E67FB-EB7B-4569-BD77-89DDEDDED471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1883661$EE552C7A-2D49-476B-ABF6-D7B9189C9B75","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":"Q1883661$8A8F2312-08D6-4F2F-B253-42D51EF25C3C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a2b21c863dd4764da3efa26461cbf4ce03ed04ec","datavalue":{"value":"bafkreibsbqosm3upgqe4hpgbkozf7bzajqic4ozll7talszmc3tb3tg7ju","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1883661$B25FAEEA-F429-42AD-8FC8-AC5472170378","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df8dd35b2c1566f4a0628f238ff3f5c96c70ea0d","datavalue":{"value":{"entity-type":"item","numeric-id":4210668,"id":"Q4210668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b02b760224701c385cb54631872058abd175b98","datavalue":{"value":{"amount":"+0.8513485193252563","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":"Q1883661$6E55C65A-2AF8-4EFB-B2BB-BA1534E1F3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e4465ee21ebfc676d994df41e9cf48ca57be343","datavalue":{"value":{"entity-type":"item","numeric-id":4667604,"id":"Q4667604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c50108b737a389d5677d05382356b52ec4f3fd69","datavalue":{"value":{"amount":"+0.8126564621925354","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":"Q1883661$CA20D94E-A3DA-4215-895B-4A709A60570C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04d436114d056d15172d896276dc0de16310669","datavalue":{"value":{"entity-type":"item","numeric-id":1283792,"id":"Q1283792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58aca9130db4633580fde87b9a96dc75c624c88a","datavalue":{"value":{"amount":"+0.7985744476318359","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":"Q1883661$E8BDA407-4B0E-4386-A6BE-C2759FC40C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"020f63fd44b5a78e89d7cb78986512091d155f26","datavalue":{"value":{"entity-type":"item","numeric-id":1057062,"id":"Q1057062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11ecfac57f61d67e20cb48118909ef9f3d65dfaf","datavalue":{"value":{"amount":"+0.7979629039764404","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":"Q1883661$3C4531F6-AF7B-4FA0-945F-943235E34300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21e7b545e2476a60b9829d19ecfacce5660ce148","datavalue":{"value":{"entity-type":"item","numeric-id":5501285,"id":"Q5501285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2150246094ccd6da9add2c1ad4c67db0a54e4acd","datavalue":{"value":{"amount":"+0.797341525554657","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":"Q1883661$477DFE3C-6C5C-4E0D-BE5F-096A7BAA7A4B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Vertex-partitioning_into_fixed_additive_induced-hereditary_properties_is_NP-hard"}}}}}