{"entities":{"Q1874371":{"pageid":1885113,"ns":120,"title":"Item:Q1874371","lastrevid":73049814,"modified":"2026-04-14T09:53:05Z","type":"item","id":"Q1874371","labels":{"en":{"language":"en","value":"Independent sets of maximum weight in (\\(p,q\\))-colorable graphs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1915552"}},"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":"Q1874371$6173F390-9CF2-4787-AE12-A89C42208982","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fff51d4360a222272aeb13be3485667b9ffd374","datavalue":{"value":{"text":"Independent sets of maximum weight in (\\(p,q\\))-colorable graphs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1874371$1236AD1F-9EE8-4250-9FEA-C6083C9B6049","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7bed1746d6aff1d88b34751e8bd2bded6f4c96e6","datavalue":{"value":"1034.05020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1874371$200938E8-6E98-4981-AECF-C44A09246535","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"820de16e587e94bf0a4446b07803fc68cefcf960","datavalue":{"value":"10.1016/S0012-365X(02)00877-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1874371$0F985A9F-40CE-4A4F-9A16-6EF55AEDA37E","rank":"normal"}],"P16":[{"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":"Q1874371$74E4DE81-FF61-4C36-BD21-D851F3CE19AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6eb2cb381256651b6c689bf39a2d84a61c7c154","datavalue":{"value":{"entity-type":"item","numeric-id":705490,"id":"Q705490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$964159C7-17B5-4ABE-8BAC-0FCBBD4DB340","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$03D48DAE-26A8-473F-8DCD-3132083EEFB4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"68a6a59edb1a41421171fc7a476d9d545e0612d5","datavalue":{"value":{"time":"+2003-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1874371$2DA7FCA1-B6E0-4D15-B144-EA98AFAFC8F5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e40143bd36218c0719d18ef60dfab64d4b7020b","datavalue":{"value":"The authors consider \\((p,q)\\)-colorable graphs (their vertex sets can be partitioned into at most \\(p\\) cliques and \\(q\\) independent sets). In particular, \\((0,2)\\)-colorable graphs are bipartite, and \\((1,1)\\)-colorable are split graphs. For both of these classes, the problem of finding a maximum weight independent set is known to be solvable in polynomial time. In this note the authors give a complete classification of the family of \\((p,q)\\)-colorable graphs with respect to time complexity of this problem. Specifically, they show that the problem has a polynomial time solution in the class of \\((p,q)\\)-colorable graphs if and only if \\(q \\leq 2\\) (assuming \\(\\mathcal{P} \\neq \\mathcal{NP}\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1874371$8431A79A-2FA8-49C4-B2E2-31A75A66E32B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e6413b5cad0c7e768ddd93cf1b189675e97f5dbf","datavalue":{"value":{"entity-type":"item","numeric-id":228794,"id":"Q228794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$49466FB0-8000-4E5E-8821-6945A552AA9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1874371$54E7A521-EA5B-4AB9-8878-E309DB57C9FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1874371$CA4AB758-EF89-42CE-988F-9EC58E461003","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3d4b3c0b996eadf2adf68dd602a8e1607e1bada","datavalue":{"value":"1915552","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1874371$0A0BF8CE-4CAF-45D5-BA66-404F09A311AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58870da1a411fbaea967c29271b1a9178ff50ec1","datavalue":{"value":"weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1874371$E839DFB1-10D9-4A45-A84F-3D4452E7CDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1874371$6D304E50-A5C2-4C4C-8AEA-B4EE03BF702E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1874371$7D1CECC2-90A0-4266-8BA9-8C815BEDDF55","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":"Q1874371$B04CEB3C-1D81-4262-8D74-20CFD568F6F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"078b931a9fe3dac15986eadf2f67608aa760ec66","datavalue":{"value":{"entity-type":"item","numeric-id":3809822,"id":"Q3809822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$E8797B78-2964-4F59-9932-F5A722379289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24ab94925d77f68bbba9bb500216729d0045622e","datavalue":{"value":{"entity-type":"item","numeric-id":1363736,"id":"Q1363736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$E7A5ACD3-062D-4448-8F47-60F8F7470BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$11505B57-5C70-4586-A55A-CAB404AF3CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7ce59828600cc233a688431399aa1fded1625e6","datavalue":{"value":{"entity-type":"item","numeric-id":1073049,"id":"Q1073049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$17BA0A30-8C60-4399-B130-CD34ADE1CBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$7E5E39D3-CD7C-4BDF-9687-BEE39255A801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0755527dc26ccf06e69cd62ec76a91e4b8d0335c","datavalue":{"value":{"entity-type":"item","numeric-id":3903002,"id":"Q3903002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$58F96CF9-5E8F-491E-B8B3-EF100711736C","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":"Q1874371$D4C1786C-F593-4556-A067-03274803E2A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$F05DA4D3-99DC-43F8-B355-3AE2BD60427F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$79541FB8-D4F1-40E7-A0B3-94FC9914558E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6033cbdfc75fbf185f01d24946516a20af7924a6","datavalue":{"value":{"entity-type":"item","numeric-id":4483540,"id":"Q4483540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$7A356781-DA8E-49FE-A6BA-D2128985C0F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ccf2ce6ffe932287a3e8f6d3b281b44fd4ad0eb","datavalue":{"value":{"entity-type":"item","numeric-id":4770411,"id":"Q4770411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$BEEC8834-7D16-4C5D-AFA8-ED3918E6C530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fb2f096723aaf6bf70a3284ee1f70fbd9ce59ae","datavalue":{"value":{"entity-type":"item","numeric-id":4871056,"id":"Q4871056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$C9FAF13F-C179-4DD2-BCDD-31D50D8842EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$76C87B67-6E42-4338-8C3D-0D532DBFC102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb85e2a08b123210f7ea1cf8a8c1c958121dd184","datavalue":{"value":{"entity-type":"item","numeric-id":4138754,"id":"Q4138754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1874371$23ABD7AE-55E9-4D75-95B4-F3A57E2A3B35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ff0fab682047c36f5ec290c85d8e1b8651d5b43f","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00877-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1874371$E6650352-A565-4507-BF6A-DA88994AD515","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1c6ba9f6ee5a5a1b3de3f584c7ee5b7cf5416fc","datavalue":{"value":"W2096226903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1874371$B04FADDF-C74C-443C-AE31-CE96E276AC11","rank":"normal"}],"P1643":[{"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":"64d41cf506fc21844143df3037bb9750c329d50f","datavalue":{"value":{"amount":"+0.7973492741584778","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":"Q1874371$C138D9D5-20E4-4899-B751-6CD756F2EFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ebe1e6bd34c0111f5b31fa9f5e60b7329529a49","datavalue":{"value":{"entity-type":"item","numeric-id":1755775,"id":"Q1755775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2785ce3676626b26f1679b1e2eb575e10351142d","datavalue":{"value":{"amount":"+0.7676739692687988","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":"Q1874371$AAB8A3B5-411F-4290-B270-8D27B9FF74EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dacb34205e7371f7ce0615d01d11761b985f0ef2","datavalue":{"value":{"entity-type":"item","numeric-id":344862,"id":"Q344862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"702057951ea26ea8f1f17e9e265597fc6c4d2e61","datavalue":{"value":{"amount":"+0.7671570181846619","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":"Q1874371$3F20601B-96E7-409B-BE59-45737117CBD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382e5e936b64cdde8dff44a36586470c4db4dab7","datavalue":{"value":{"entity-type":"item","numeric-id":2864316,"id":"Q2864316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90d843418aae62923d8568708e3d1676d8008191","datavalue":{"value":{"amount":"+0.7666495442390442","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":"Q1874371$3DAD5513-36DF-4BCB-A1FF-9E73895DB879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd558e82588c315198ec4fdf4bcea88d268b5bb9","datavalue":{"value":{"entity-type":"item","numeric-id":4301637,"id":"Q4301637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bb3a2e7326e8f3edbc49870fd6a263f554f1429","datavalue":{"value":{"amount":"+0.7649546265602112","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":"Q1874371$8C9810FD-D962-4FC4-9AA5-7F747B46860B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independent sets of maximum weight in (\\(p,q\\))-colorable graphs.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Independent_sets_of_maximum_weight_in_(%5C(p,q%5C))-colorable_graphs."}}}}}