Perfect matching cuts partitioning a graph into complementary subgraphs

DOI10.1007/978-3-031-06678-8_19arXiv2210.06714MaRDI QIDQ6413792FDOQ6413792

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

Publication date: 13 October 2022

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.

Mathematics Subject Classification ID

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

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)