Perfect matching cuts partitioning a graph into complementary subgraphs (Q6996465)

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?