{"entities":{"Q2368935":{"pageid":2379678,"ns":120,"title":"Item:Q2368935","lastrevid":43966254,"modified":"2025-11-18T14:30:36Z","type":"item","id":"Q2368935","labels":{"en":{"language":"en","value":"On NP-hardness of the clique partition -- independence number gap recognition and related problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5020349"}},"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":"Q2368935$013220F5-7AFC-4DFC-804B-BDFAB574B489","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55f8e04620f84889e75c722c59b66c8f2573c465","datavalue":{"value":{"text":"On NP-hardness of the clique partition -- independence number gap recognition and related problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2368935$A456C3EE-17AC-4435-99E9-3EA188659ED1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c2ee2eaf4514b2cfb60fa7ac672967c0fe4ba09","datavalue":{"value":"1091.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$A2FEE36C-1DF8-4597-8670-3014A4BD6B7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a52160bab52fceb84dca622e1b7e4a7ba794cb2","datavalue":{"value":{"entity-type":"item","numeric-id":604869,"id":"Q604869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$437D6804-A3D8-465A-BD51-B1833C23C1FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f53c5105382fd16c61f122c2d812e58329b86fc","datavalue":{"value":{"entity-type":"item","numeric-id":674620,"id":"Q674620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$477C25CB-E85F-44DE-91E1-EDA3CA84E4B2","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":"Q2368935$5A7CE624-B4B4-4D74-94D3-F35C11DE21F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8728e91b2b3c919aca654c671fc4eed9ec21fc4b","datavalue":{"value":{"time":"+2006-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2368935$2F554DD5-169C-4F28-B9C5-EB789C68878C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e562996332a86d319c7f60ad5c7da12592873207","datavalue":{"value":"The clique partition number \\(\\overline\\chi(G)\\) of a graph \\(G\\) is defined as the minimum number of cliques which partition the vertex set of \\(G\\). The independence number \\(\\alpha(G)\\) is the maximum number of vertices of \\(G\\) such that no two of them are adjacent. It is well known that \\(\\alpha(G)\\leq\\overline\\chi(G)\\) while both \\(\\alpha\\) and \\(\\overline\\chi\\) are NP-hard to compute.   The authors of this note prove that it is NP-hard to decide whether \\(\\alpha(G)<\\overline\\chi(G)\\) for a graph \\(G\\) even when a partition of its vertices into \\(\\overline\\chi(G)\\) cliques is given. Equivalently, this result states that given a graph \\(G\\) and a coloring of its vertices with \\(\\chi(G)\\) colors, it is NP-hard to decide whether \\(\\omega(G)<\\chi(G)\\), where \\(\\omega\\) and \\(\\chi\\) denote the clique and chromatic numbers, respectively. The proof is based on a reduction from the problem of completing partial Latin squares, whose NP-completeness was proved by \\textit{C. J. Colbourn} [Discrete Appl. Math. 8, 25--30 (1984; Zbl 0538.05013)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368935$9C4F73F6-2341-4F85-A342-652AF7A91ECB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c0617d45f23e5dfc7fb0eb4ddcab2f46301293e8","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$1FF45D55-6123-4F36-AF4B-A22525392F8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$BC98E19C-A3F6-4F33-A9FC-47C9951A3A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$471DFF2F-1F49-43A1-A83E-9175F2E1F92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$B4D648E0-2426-4004-BD56-6D178E655840","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c47297bcd6bd97bdce9997f7ae93c0df4ffd73b","datavalue":{"value":"5020349","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$1675E358-9DF7-4D6F-B2C4-E0A40B853145","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7055ef5785d9ad8b332e447e19065da135370950","datavalue":{"value":"partial Latin squares completion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368935$F1B8EB05-0D78-4055-B079-7F69F260E9D4","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":"Q2368935$35DD9D7E-090C-45C5-8712-6B06E73A8161","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0bec804da0c0694cd3606d28135f32b5988c9dfb","datavalue":{"value":"Q56874375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$B5AB8A6E-3451-41DD-8910-8127E84DD0F8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c595798d55f6230fee678e0ee38dcf2a72ff2ba","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.01.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q2368935$F9F124A9-8C78-42CF-9A67-61FD0F454390","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e052c33e31d85b2d53430628ff3f7f7bf6ec6eb2","datavalue":{"value":"W1986997293","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$90A676CB-5C86-4B76-B743-91112999F3F7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ed1e3868cfed1b6749cf6e45a29b73a0b33c3dc","datavalue":{"value":{"entity-type":"item","numeric-id":3218140,"id":"Q3218140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$43353F68-C3F6-47DA-A453-67F5C1C6BFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44df457be70f86c1f418ff54b4fd473088692edc","datavalue":{"value":{"entity-type":"item","numeric-id":793029,"id":"Q793029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$5D9B3A1A-E9BC-4033-B620-DC9891DCF748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"414fb81d4fcd145875bf7003f9e7ef9d374876b5","datavalue":{"value":{"entity-type":"item","numeric-id":2784442,"id":"Q2784442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$F3FA4552-4E36-43AA-BED3-CD8BCB0C9049","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":"Q2368935$DFB00C7B-BED7-4F77-97AB-4B53A90691A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afa702fec73d3c71a5ae58273031bf0348da44e4","datavalue":{"value":{"entity-type":"item","numeric-id":1365053,"id":"Q1365053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$7317416B-C7CF-4F3B-B96B-E32D5B87C8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7501f20b834ad31ac34e94ecf711a5acc9b3a290","datavalue":{"value":{"entity-type":"item","numeric-id":5710226,"id":"Q5710226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$152E47A9-1D69-402C-B047-8A3A490C547F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1df61c4df8f812c83e621e524aa24458422ccaf1","datavalue":{"value":{"entity-type":"item","numeric-id":2741510,"id":"Q2741510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$A8C2CE80-C358-4A66-AC10-014DA3775AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"139f7aa6e8ee8bfb6c751d0c7184b11208f7993f","datavalue":{"value":{"entity-type":"item","numeric-id":1344393,"id":"Q1344393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$A7B03A9F-4967-4AC7-ACE4-D7EBF1D03489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a48c289367846d2e6cbf6ff475cf182266d6c35","datavalue":{"value":{"entity-type":"item","numeric-id":4178914,"id":"Q4178914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$5768D58A-D56A-498C-A4FB-A96D26F59108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c94d017d89fe8a00bee910dd24c96d75202f025b","datavalue":{"value":{"entity-type":"item","numeric-id":4012419,"id":"Q4012419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368935$B88CE901-739C-4B61-8C5F-DFEE4C1B24EE","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"862615363d0460b27808d18ecf56489308de9fdd","datavalue":{"value":"journals/dm/BusyginP06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$D93C1377-47AB-414D-991A-BF43E75F9BBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"27f3be7b152a0befc40a9d6130ab176498251abf","datavalue":{"value":"10.1016/J.DISC.2006.01.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368935$E2382C52-08F3-4569-8FA8-865A4AD991A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c12167cb37ba4115a401076b0e02a22b2d1abea","datavalue":{"value":{"entity-type":"item","numeric-id":4734765,"id":"Q4734765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45b02115e7af06d14fc0128f50daa87ac113e6c8","datavalue":{"value":{"amount":"+0.9028887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$19D6D4F2-3C70-4288-AF17-12CB1E52E9B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7d3bd78e153efe0694fbe93c9bca848a35d52b8","datavalue":{"value":{"entity-type":"item","numeric-id":3772258,"id":"Q3772258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c2ae75ce274b7cc2d866e5955507937997be715","datavalue":{"value":{"amount":"+0.8923104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$F47EE3E6-5CB0-4ACC-8C23-68EE775DCD96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"256c3b57f5930647fe226fe8fcc17e703390e748","datavalue":{"value":{"entity-type":"item","numeric-id":516874,"id":"Q516874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9344b2348c14cc5c6b0ab6523313b7d68710350","datavalue":{"value":{"amount":"+0.8843181","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$A864A51E-F9DB-441F-B76E-35EF2B276FC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85487daccbd6efd236401fa1d0df8dab8f21fc5e","datavalue":{"value":{"entity-type":"item","numeric-id":2174276,"id":"Q2174276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fd5b1727e9bd01d7a323f1b45391cc04cbae433","datavalue":{"value":{"amount":"+0.8807889","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$4BF3E9F5-1BF6-4371-9889-95046A083243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cd924c55feb753b6f5a766bbd7e43b50e0084d5","datavalue":{"value":{"entity-type":"item","numeric-id":1709587,"id":"Q1709587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36ddb515937b879a5cbe7ceafbdab69cfb37a29d","datavalue":{"value":{"amount":"+0.88014394","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$73E3D783-239E-4D4A-9BC7-615CFFB74561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cb7d47219d55449db11d051f67382f8d78651c4","datavalue":{"value":{"entity-type":"item","numeric-id":2946384,"id":"Q2946384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c80817d70c864953f3c21541915e8ada64ae2591","datavalue":{"value":{"amount":"+0.8801439","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$69FDC86F-0CA1-47CC-9D22-B26648B43F0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1359fef12758c9cb87931b7f8e42c1f326d58345","datavalue":{"value":{"entity-type":"item","numeric-id":2800551,"id":"Q2800551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fbda6ad54438f3ac071f037cd428df88cea4af8","datavalue":{"value":{"amount":"+0.8784032","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$AF6E6FBE-A4DB-4B69-8CA1-A5D438CBA801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8430567af32487215f3e704732c40aa60a8f2730","datavalue":{"value":{"entity-type":"item","numeric-id":2775896,"id":"Q2775896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af2ccb1e900c7550df5746faa64268537fe8c858","datavalue":{"value":{"amount":"+0.87663245","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$5E1E55B2-A78B-44BB-A8C1-DA8616A69180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69bc352a432b87df69859ad5e3450a9b5ada7e2d","datavalue":{"value":{"entity-type":"item","numeric-id":2095085,"id":"Q2095085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7f58cdcca90d0ff905c9cea4c1b38a685fcc026","datavalue":{"value":{"amount":"+0.8755636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$BD86C97B-3090-4EE0-8ACC-4F9F0679658A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1eb62f6b93bcceeece15b362f6523d2dbc58335f","datavalue":{"value":{"entity-type":"item","numeric-id":1799389,"id":"Q1799389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2aadd57ca89677055596564cace8ce6e549a6108","datavalue":{"value":{"amount":"+0.87273127","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2368935$769DEA71-F6D0-4400-B29B-EAEA087B25C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2368935","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2368935"}}}}}