Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs

Felicia Lucke, Ali Momeni, Daniël Paulusma +1

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 studie…