Perfect matching cuts partitioning a graph into complementary subgraphsCastonguay, Diane (Avtor) Coelho, Erika M. M. (Avtor) Coelho, Hebert (Avtor) Nascimento, Julliano R. (Avtor) Souza, Uéverton S. (Avtor) graph partitioningcomplementary subgraphsperfect matchingmatching cutgraph isomorphismIn PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB) we are given a graph G = (V, E), and an edge set property Π, and asked whether G can be decomposed into two graphs, H and its complement H̄, for some graph H, in such a way that the edge cut [V(H), V(H̄)] satisfies the property Π. Motivated by previous work, we consider COMP-SUB(Π) when the property Π=PM specifies that the edge cut of the decomposition is a perfect matching. We prove that COMP-SUB(PM) is GI-hard when the graph G is C_5-free or G is {C_k ≥ 7, C̄_k ≥ 7}-free. On the other hand, we show that COMP-SUB(PM) is polynomial-time solvable on hole-free graphs and on P5-free graphs. Furthermore, we present characterizations of COMP-SUB(PM) on chordal, distance-hereditary, and extended P_4-laden graphs.Založba Univerze na Primorskem20252025-10-21 22:25:20Članek v reviji21992UDK: 51eISSN: 1855-3974DOI: https://doi.org/10.26493/1855-3974.3015.f4asl