{"entities":{"Q6996465":{"pageid":21481779,"ns":120,"title":"Item:Q6996465","lastrevid":76419390,"modified":"2026-04-24T01:07:46Z","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"}]},"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"}}}}}