Perfect matching cuts partitioning a graph into complementary subgraphs

DOI10.1007/978-3-031-06678-8_19MaRDI QIDQ6413792arXivFDO

Authors Diane Castonguay, Erika M. M. Coelho, Hebert Coelho, Julliano Rosa Nascimento, Uéverton S. Souza

Publication date 13 October 2022

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Abstract: 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 its complement $overlineH$, for some graph $H$, in such a way that the edge cut $[V(H),V(overlineH)]$ satisfies the property $Pi$. Motivated by previous work, we consider Comp-Sub($Pi$) when the property $Pi=mathcalPM$ specifies that the edge cut of the decomposition is a perfect matching. We prove that Comp-Sub($mathcalPM$) is GI-hard when the graph $G$ is $C_{kgeq7},overline{C}_{kgeq7}$-free. On the other hand, we show that Comp-Sub($mathcalPM$) is polynomial-time solvable on $hole$-free graphs and on $P_5$-free graphs. Furthermore, we present characterizations of Comp-Sub($mathcalPM$) on chordal, distance-hereditary, and extended $P_4$-laden graphs.

This page was built for publication: Perfect matching cuts partitioning a graph into complementary subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6413792)