{"entities":{"Q1283792":{"pageid":1294542,"ns":120,"title":"Item:Q1283792","lastrevid":70575651,"modified":"2026-04-13T15:33:16Z","type":"item","id":"Q1283792","labels":{"en":{"language":"en","value":"Generalized partitions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1271070"}},"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":"Q1283792$7C24D73F-3D87-48DE-90C3-9946C9DF4B95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"85e684a6ed7962b2fe3bb78ad39acd0c1bb23568","datavalue":{"value":{"text":"Generalized partitions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1283792$9E829EE6-45AC-4021-BF45-5FC2B8F47258","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c32947ab3a89f45f78000f3419df7c88f38372e0","datavalue":{"value":"0917.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$AEA420D9-8C57-449F-9E9D-94B0D58F8469","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f21df19662667fa7793f40f4e2243cd59d43b477","datavalue":{"value":"10.1016/S0166-218X(98)00124-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$E94DE96F-32D6-450D-8358-9D3C29D481B9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"57555e49e581043524b19e8ff224491cb25ceec4","datavalue":{"value":{"entity-type":"item","numeric-id":189757,"id":"Q189757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$9550E31B-D0A5-495A-B4B5-84E2B4A52694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4967ea9304b5b3e6f0d66c933c16be82f21ad0d7","datavalue":{"value":{"entity-type":"item","numeric-id":476893,"id":"Q476893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$4843DA37-9DC3-4A8C-9926-E8A1535E4288","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$D58BF07D-6038-426C-8353-6FBC73D5B21D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"15e79b911281d7335b148829a2415cb4e1e39b23","datavalue":{"value":{"time":"+1999-07-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1283792$FF964ADE-86BE-42F7-A268-7CF446DDFAB2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"697ac596dc961fa69f053a0489794e56d36d84c5","datavalue":{"value":"The authors introduce a general graph partitioning problem: Let \\(C\\) be a class of graphs and \\(H\\) a fixed graph with vertex class \\(V(H)=\\{1,2,\\dots,n\\}\\). An (resp. ONTO) \\((H,C)\\)-partition of a graph \\(G\\) is a partition \\(V_1,V_2,\\dots,V_n\\) of \\(V(G)\\) such that, for each \\(i\\), the subgraph of \\(G\\) induced by \\(V_i\\) belongs to \\(C\\) and, if \\(i\\neq j\\in V(H)\\), there is an edge with one end in \\(V_i\\) and the other in \\(V_j\\) (resp. if and only if \\(ij\\in E(H)\\)). Let \\(K\\) be the class of all complete graphs including the empty graph, \\(K'\\) the class of all complete graphs excluding the empty graph with the class of vertices being empty. Let \\(B\\) be the class of all complete bipartite graphs with at least one edge, together with \\(K_0\\) and \\(K_1\\). \\(S\\) is the class of all stars. A prime denotes the same class of graphs, excluding the empty graph. It is proved that if \\(H\\) is a triangle-free graph, then the \\((H,K)\\)-partitions, \\((H,K')\\)-partitions, ONTO \\((H,K')\\)-partitions, \\((H,B)\\)-partitions, \\((H,B')\\)-partitions, ONTO \\((H,B')\\)-partitions, \\((H,S)\\)-partitions, \\((H,S')\\)-partitions, and ONTO \\((H,S')\\)-partitions are polynomial. If \\(K_3\\) is a subgraph of \\(H\\), then the \\((H,K)\\)-partitions, \\((H,K')\\)-partitions, ONTO \\((H,K')\\)-partitions, \\((H,B)\\)-partitions, \\((H,B')\\)-partitions, ONTO \\((H,B')\\)-partitions, \\((H,S)\\)-partitions, \\((H,S')\\)-partitions, and ONTO \\((H,S')\\)-partitions are NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$4B0E48C9-BFAD-4E2B-8CED-75B15F1BC885","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$DFCC7464-866A-402A-A8AE-870609098F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$CB9A3F68-87F8-4CCE-BFAE-3F81CBA7921B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$068A6230-284D-4C6F-98EF-8A09F686805B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$2894B6A4-58A9-4CAA-AF45-0EA9264999FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5029b0841524fb1b52945933877aa119fb6461b","datavalue":{"value":"1271070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$3A3CEF4F-D866-4FAD-9D81-497B63966696","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d960d3503ffdd20aafd92156ed8a89368ace3d85","datavalue":{"value":"conditional coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$DDB7C6E0-3B1D-46A8-9B81-F626B1FF7104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afae4036665b55006e97ddb95810db2989e6b0f2","datavalue":{"value":"2-sat","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$0914AF2A-70E0-4A39-ABD3-5395532E3DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$0C7C25EA-8CA7-400E-B8B4-3163A75E7A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$3976D49E-CE0B-4E10-A553-10C0446463CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$E4A35D05-4706-44D5-ADF2-C244EB3645DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283792$E329944E-6EB0-4C64-A256-8D24DAA3B26D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a0c162be9cf44925bccf6e1c399095c6b68814d1","datavalue":{"value":{"entity-type":"item","numeric-id":237118,"id":"Q237118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$58BCC928-00FF-4702-A1A5-52523B278EC0","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":"Q1283792$B4ADF2E5-4947-40C4-8BC6-1FA881A12597","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ae2bbd128c0328314f0cb44ba6d2131fc918aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3688407,"id":"Q3688407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$27DBCA84-1AAC-45E8-A4F9-D81A7F50D597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b3146341f0fd2377f313f4028df6fdb8adcedd9","datavalue":{"value":{"entity-type":"item","numeric-id":3739139,"id":"Q3739139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$1EB338F6-9825-4B3D-9706-E3BAEE901F57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2def493c6145889772ddbfb9ee64a57941dd9a7","datavalue":{"value":{"entity-type":"item","numeric-id":3748295,"id":"Q3748295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$765FBBDF-6029-42F9-B5C6-2709289B0734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3de7edad0b76fa41f3d5b9d1b0f37d5e44dc7a8a","datavalue":{"value":{"entity-type":"item","numeric-id":1166429,"id":"Q1166429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$C509840B-DDA8-4854-BE0B-7B7C861E51AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e97d78f2ad211155ffa5d6f2138c431781f03354","datavalue":{"value":{"entity-type":"item","numeric-id":1145707,"id":"Q1145707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$A51AF79F-8B26-41DF-A162-28FD30F4E2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63a15d5dd23bf19a39aa8a8cda6054963a62040b","datavalue":{"value":{"entity-type":"item","numeric-id":3760563,"id":"Q3760563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$248ADCD7-CD2B-4DFD-9883-2D31FAE58AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$E396A5F6-8E1C-4FCA-B278-0AF8FB4854AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$F090FAC9-580A-483F-8CC0-AE00BE4E667B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d0c3c0703de8c7498c1e8ddecb6199c9702f15b","datavalue":{"value":{"entity-type":"item","numeric-id":3220612,"id":"Q3220612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$2FB42195-76FA-411D-ABCE-E2453704B99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b14233efbc23e31889365df721ca3ba294a25b","datavalue":{"value":{"entity-type":"item","numeric-id":5402563,"id":"Q5402563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$3544782D-B0E6-4285-BCC9-01EEF582AF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a259690ae283b3d41549f2793a233a2898cf4590","datavalue":{"value":{"entity-type":"item","numeric-id":1149783,"id":"Q1149783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$7F13EA73-8AA1-48F1-A373-62C6D324B0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a73af81ab888b2965fe460eabf7089afc50641c","datavalue":{"value":{"entity-type":"item","numeric-id":3038617,"id":"Q3038617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$8EB95292-98CE-4D1D-9317-C382576F24D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b97f750e9c8b6509ac6238c920a51525b82dd93","datavalue":{"value":{"entity-type":"item","numeric-id":1068852,"id":"Q1068852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$96F4AA4F-B84B-4ED5-BF60-2C5FBC4FA71C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3394c99d289eba45168ce7a791f0a5170c18bb41","datavalue":{"value":{"entity-type":"item","numeric-id":3728943,"id":"Q3728943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$E5EF0683-663F-4F74-A45B-70D5CF791C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783152774ce8a73592a05f95c5c22effc929a518","datavalue":{"value":{"entity-type":"item","numeric-id":3825107,"id":"Q3825107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$B33FF8AB-A4CD-4C25-B689-6673F4251DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$1EE4B932-C3F4-45DD-B28D-59C0C914C3D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ae06ace3264ebdef666fd198a2d1441400a748e","datavalue":{"value":{"entity-type":"item","numeric-id":4087195,"id":"Q4087195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283792$035F3D1A-809D-4159-A629-6F39C9650F0A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9485dba198cadf9879d1be5cb445ae64aab5349c","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(98)00124-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1283792$D4CACA35-E752-4597-8102-54D678BFEBD6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"15cabb4c593f0def569571f22b0bf86e1ddc9521","datavalue":{"value":"W2149498497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$E5626559-0E63-4689-B180-57C11629A911","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b849fa458f0befede5876a16b05bb68ea7d1157a","datavalue":{"value":"Q126440158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283792$3706256C-3BF5-4BDA-B91D-7F062112FC1D","rank":"normal"}],"P1643":[{"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":"016681cb4445ac84f2b4582dd1c52520f0aab547","datavalue":{"value":{"amount":"+0.8356449604034424","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":"Q1283792$62143167-7F55-4164-B7B7-2964E26C4C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd14f14fb59fbc338421a338cd62ac6b05c7444d","datavalue":{"value":{"entity-type":"item","numeric-id":3544241,"id":"Q3544241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ee1df2f077f62796808f2ef34480f2a4abcf0e0","datavalue":{"value":{"amount":"+0.8338006138801575","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":"Q1283792$F192AFC7-6771-49A3-8197-CF960AD61F70","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":"86035ca1b0297c89c3bc78cc97a0b738cc238c28","datavalue":{"value":{"amount":"+0.82325679063797","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":"Q1283792$136E7B6E-8362-467D-9FF5-25EAA4BD4B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30341af331d603056fc59434cf2f9f6fa12fc492","datavalue":{"value":{"entity-type":"item","numeric-id":3731031,"id":"Q3731031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5718fa575554af00963c23ff6e2ca1f3e320dbd","datavalue":{"value":{"amount":"+0.8222342729568481","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":"Q1283792$F4A8BD0E-3E93-4676-B017-BA6661661D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12618c0e212bea0f0592a283a5af8c2917ead031","datavalue":{"value":{"entity-type":"item","numeric-id":2352776,"id":"Q2352776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1a13bf4b87a024beda3f8b2dccdf1c56cc53633","datavalue":{"value":{"amount":"+0.8177040219306946","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":"Q1283792$711D71D9-D963-4A64-844D-A116A66AA639","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized partitions of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_partitions_of_graphs"}}}}}