| Title: |
On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs |
| Authors: |
Lucke, Felicia, Paulusma, Daniël, Ries, Bernard |
| Publication Year: |
2022 |
| Subject Terms: |
Mathematics - Combinatorics, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms |
| More Details: |
For a connected graph $G=(V,E)$, a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most $d$ if $d\leq 2$ and NP-complete if $d\geq 3$. We prove the same dichotomy for graphs of bounded radius. For a graph $H$, a graph is $H$-free if it does not contain $H$ as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for $P_6$-free graphs, extending a recent result of Feghali for $P_5$-free graphs. We then extend our result to hold even for $(sP_3+P_6)$-free graphs for every $s\geq 0$ and initiate a complexity classification of Matching Cut for $H$-free graphs. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2204.07129 |
| Accession Number: |
edsarx.2204.07129 |
| Database: |
arXiv |
