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≥2, d-Cut is polynomial-time solvable for graphs of diameter 2, (P3+P4)-free graphs and P5-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 partial dichotomies for H-free graphs; for d≥3, our classification of d-Cut for H-free graphs only has three open cases.