{"entities":{"Q6996465":{"pageid":21481779,"ns":120,"title":"Item:Q6996465","lastrevid":83782889,"modified":"2026-05-07T11:20:13Z","type":"item","id":"Q6996465","labels":{"en":{"language":"en","value":"Perfect matching cuts partitioning a graph into complementary subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8027989"}},"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":"Q6996465$92A72A42-019E-404D-BE0B-950603EB608A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2673b7c60d3deb2351899526c6a8908a05502291","datavalue":{"value":{"text":"Perfect matching cuts partitioning a graph into complementary subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6996465$D9687F67-E255-4DCA-B0E0-A16CB5F8F0CD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dcd3b90fdac289d7acb1e69a148de36b8de590ab","datavalue":{"value":"1562.05301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$E0E3F6BA-BADE-4E5E-9F9E-E26354526E82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7ce1d93a6070ed1f4dcc1df39cce79bdd3e62c1","datavalue":{"value":"10.26493/1855-3974.3015.F4A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$224A263B-00B2-409C-BA2E-F1158BCD3843","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dfb4127a82fdf1ac6637ff7f9f40f77db298bb8","datavalue":{"value":{"entity-type":"item","numeric-id":279746,"id":"Q279746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$4B90D438-5281-480E-8D47-EC1BAA75DCF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"36b37bce85b9a6e301d7a667b30f120eb600c559","datavalue":{"value":{"entity-type":"item","numeric-id":412267,"id":"Q412267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$FF1C34DC-6D82-4A46-A042-612752F5952A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9290b410674ba1482750271645a2f9f55381a8a0","datavalue":{"value":{"entity-type":"item","numeric-id":510981,"id":"Q510981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$0283C24A-B331-45EE-980C-37EE73E6988E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"51c14a9c79db85b52ae6a98363b208ac7398d8bb","datavalue":{"value":{"entity-type":"item","numeric-id":782184,"id":"Q782184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$942CED2F-6E4B-4509-9A1F-D06E81A3974D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f129b06f469a7f73a2e133b154da657c1c0ce59a","datavalue":{"value":{"entity-type":"item","numeric-id":317428,"id":"Q317428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$A87BD0DD-7698-49DC-8013-3F3BFDAC8101","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fd452cca5b00147bef63ee92f19ca6f2d3d95ab1","datavalue":{"value":{"entity-type":"item","numeric-id":2810374,"id":"Q2810374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$7159FC5C-F53D-48C9-9408-593767E8A410","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"274538285c524dd180c867022fb2166cb902801c","datavalue":{"value":{"time":"+2025-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6996465$06442DA6-F0EC-4891-B532-75727F020798","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4afa302298d3655bc2eadfb02ee658d60d71910e","datavalue":{"value":"Lately, making graph partitions with particular attributes is a topic of extensive research. In partition into complementary subgraphs (COMP-SUB) given a graph \\(G = (V, E)\\), and an edge set property \\(\\Pi\\) the question is whether \\(G\\) can be decomposed into two graphs, \\(H\\) and its complement \\(\\overline{H}\\), for some graph \\(H\\), in such a way that the edge cut \\([V(H), V(\\overline{H})]\\) satisfies the property \\(\\Pi\\). The authors consider COMP-SUB\\((\\Pi)\\) when the property \\(\\Pi = \\mathscr{PM}\\) specifies that the edge cut of the decomposition is a perfect matching and prove that COMP-SUB(PM) is GI-hard when the graph \\(G\\) is \\(C_5\\)-free or \\(G\\) is \\(\\{C_{k \\geq 7}, \\overline{C}_{k \\geq 7}\\}\\)-free. They also show that COMP-SUB(PM) is polynomial-time solvable on hole-free graphs and \\(P_5\\)-free graphs and presented characterizations of COMP-SUB(PM) on chordal, distance-hereditary, and extended \\(P_4\\)-laden graphs. They conclude the article with open problems such as a) Can COMP-SUB(PM) on \\(C_k\\geq 6\\)-free graphs be solved in polynomial time? b) What is the complexity of COMP-SUB(PM) on \\(P_6\\)-free graphs? c) Is COMP-SUB(PM) complete?","type":"string"},"datatype":"string"},"type":"statement","id":"Q6996465$C9AB3F87-082A-4AF5-B872-0FA7E4F17B14","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$84D1ED4B-693C-412F-92EC-54023106F848","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$7DA4E9F5-9C61-4015-A709-11F83BE5E116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$A015D3FD-1D38-43E4-86F7-E13FF4C05F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$4C8A693A-F028-4FA4-81F1-6615072D74E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"abea942f78d2e1371fc37b811435f5f387392a55","datavalue":{"value":"05C51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$2D957968-4C6B-4A65-8751-D151A44197D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$D64D421A-EC32-4AD8-955D-39870054F17B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91a99141dafcf5f65b2cc73b038fd0b885d14579","datavalue":{"value":"8027989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6996465$DBDD02FC-B3B9-4EFD-BE13-99F0951886A4","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$82AC1EB4-EF4E-4291-AE36-775BF4FF0FF0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q6996465$B077F704-4B16-433D-BAC8-04BA5058DC7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c694425b1db6a4da8fbf8c4705cdb2b413ec4b35","datavalue":{"value":"complementary subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6996465$AB53E817-6F1A-4674-9A00-35BC71D4D337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q6996465$EEDB9F0C-90D0-40FC-82CA-6B53F47824CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5abbe2608084a7972c2175afb25edf2be63f2b","datavalue":{"value":"matching cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q6996465$C963FBB6-D39E-4BAC-8DB3-DABAD9278C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q6996465$AE96ED3F-379A-4D9A-8A6C-28ABC741B9AF","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":"Q6996465$C4EC0812-7F53-4CC9-9466-E500AF54D8BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$AB50775D-3F65-40E5-BF51-3883C2EBEFCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5926ed2235e927aab9f6e35530f911591ab32102","datavalue":{"value":{"entity-type":"item","numeric-id":5747404,"id":"Q5747404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$E683F320-A1DF-4FA2-B6B0-F3AB3B125193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac7e5375d1762c35b1b2ebc59891cf9fde29f86c","datavalue":{"value":{"entity-type":"item","numeric-id":456142,"id":"Q456142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$0193FBA4-27FB-485E-ACE1-02DDA3C360C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b698f30a37093cb3e515d4ccc549875b81695933","datavalue":{"value":{"entity-type":"item","numeric-id":5859672,"id":"Q5859672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$CC09E8B6-CBD6-40C5-8AAF-A719668412FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f96e5349c4e49e9d1ff5b84e64bb916b7b45eb8","datavalue":{"value":{"entity-type":"item","numeric-id":389934,"id":"Q389934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$9AC1909B-61F1-4E27-8781-2024EA56B052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5890cccaa2e42ff79b9f0f2ee8067b4e5c008f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3679205,"id":"Q3679205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$B769D1FE-1020-4C22-9298-518870F9C92A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7df60897b7f36fcb755315945b431813c52a78e4","datavalue":{"value":{"entity-type":"item","numeric-id":3910010,"id":"Q3910010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$0110BA19-9BDF-4900-826A-0E9B96DA10A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$D79CBA94-4094-4E0C-97FB-9DBE114D9B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c875a6b7ab476bee00f27524ea421812895d9ed","datavalue":{"value":{"entity-type":"item","numeric-id":2348267,"id":"Q2348267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$2806820E-8612-4F8E-BC64-629725E0E99E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29ddb09f4638da0c152e70140ece4be9308c9f45","datavalue":{"value":{"entity-type":"item","numeric-id":511681,"id":"Q511681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$08E00169-0A5B-40F5-AE75-158F64FF55EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20739b57aa30b4e938bee639faf3720bed80764","datavalue":{"value":{"entity-type":"item","numeric-id":5441572,"id":"Q5441572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$9975FDE5-C155-489F-B5E0-5BD7FB1215F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"241a1495d9f3db922958b33c38f95fcce819e91e","datavalue":{"value":{"entity-type":"item","numeric-id":4209364,"id":"Q4209364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$3CA22DD2-433C-401E-9AE0-4BE6F29F99C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7439459ecfe23165afda27d4bf107f319aba0aa","datavalue":{"value":{"entity-type":"item","numeric-id":897900,"id":"Q897900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$3E20CDF8-B3C9-4009-B196-5F0C09884B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4b7b06164211f6c68080ffc216f59c6c34bbae8","datavalue":{"value":{"entity-type":"item","numeric-id":2628271,"id":"Q2628271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$F81B0F13-D0B9-4710-AD8F-5FC189F1FE99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3bcdb88c4f7d8c01175ad37a9b627d9772178e4","datavalue":{"value":{"entity-type":"item","numeric-id":2675722,"id":"Q2675722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$FD7DC34D-D68C-453E-8F9E-B911AFBA73A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e405b7fbda3f49c85188dd1e8eaf0b9f0a8ade2b","datavalue":{"value":{"entity-type":"item","numeric-id":1301738,"id":"Q1301738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$8A4098A5-185D-4256-9B68-DCE977046DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd6147164683e0b364ca06fcb0e593d9cd7396d","datavalue":{"value":{"entity-type":"item","numeric-id":5918340,"id":"Q5918340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$A5E3E2FB-162B-4F2D-800E-D612921A84F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9940c7db31ae4803d6e40c0ef99f14a099d76364","datavalue":{"value":{"entity-type":"item","numeric-id":4448767,"id":"Q4448767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$80480E9F-4D46-4B8A-8728-16EAB6F9EBA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95ecc73f214487a34a4974683a1d4377b4c8471","datavalue":{"value":{"entity-type":"item","numeric-id":1759855,"id":"Q1759855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$7F47157A-6DE2-4349-8835-9BB0902F0904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20a67235037310fdced07a1a53d42b1e0b742f96","datavalue":{"value":{"entity-type":"item","numeric-id":4553727,"id":"Q4553727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$7146D72D-5CD3-4E10-90EC-0F3678875BAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b33b51f8fdc169e4cd6d3ceebac11313370d9ad6","datavalue":{"value":{"entity-type":"item","numeric-id":4560268,"id":"Q4560268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$D0ABD1E5-BC35-4ED7-9E64-B28BF455009D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b97ec674c9801d3e945638d7eae4a8579650e83","datavalue":{"value":{"entity-type":"item","numeric-id":1427186,"id":"Q1427186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6996465$3E42FEE9-4A29-4562-B6C5-B8E1BBD1BF66","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Perfect matching cuts partitioning a graph into complementary subgraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Perfect_matching_cuts_partitioning_a_graph_into_complementary_subgraphs"}}}}}