Perfect matching cuts partitioning a graph into complementary subgraphs

Diane Castonguay, Erika M. M. Coelho, Hebert Coelho +2

In Partition Into Complementary Subgraphs (Comp-Sub) we are given a graph $G=(V,E)$, and an edge set property $\Pi$, and asked whether $G$ can be decomposed into two graphs, $H$ and…