Finding $d$-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and $H$-Free Graphs
<|reference_start|>Finding $d$-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and $H$-Free Graphs: The $d$-Cut problem is to decide if a graph has an edge cut such that each vertex has at most $d$ neighbours at the opposite side of the cut. If $d=1$, we obtain the intensively studied Matching Cut problem. The $d$-Cut problem has been studied as well, but a systematic study for special graph classes was lacking. We initiate such a study and consider classes of bounded diameter, bounded radius and $H$-free graphs. We prove that for all $d\geq 2$, $d$-Cut is polynomial-time solvable for graphs of diameter $2$, $(P_3+P_4)$-free graphs and $P_5$-free graphs. These results extend known results for $d=1$. However, we also prove several NP-hardness results for $d$-Cut that contrast known polynomial-time results for $d=1$. Our results lead to full dichotomies for bounded diameter and bounded radius and to almost-complete dichotomies for $H$-free graphs.<|reference_end|>
@article{lucke2024finding,
    title={Finding $d$-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius
  and $H$-Free Graphs},
    author={Felicia Lucke and Ali Momeni and Dani"el Paulusma and Siani Smith},
    journal={arXiv preprint arXiv:2404.11389},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.11389},
    primaryClass={math.CO cs.CC cs.DM cs.DS}
}