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\ge 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 partial dichotomies for H-free graphs; for \(d\ge 3\) , our classification of d-Cut for H-free graphs only has three open cases.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Felicia Lucke,
  • Ali Momeni,
  • Daniël Paulusma,
  • Siani Smith

摘要

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\ge 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 partial dichotomies for H-free graphs; for \(d\ge 3\) , our classification of d-Cut for H-free graphs only has three open cases.