标题： 寻找爪型图中的d-割集 显示英文标题

标题： Finding d-Cuts in Claw-free Graphs

摘要： 匹配割问题是要决定一个连通图的顶点集是否可以划分为两个非空集合$B$和$R$，使得$B$和$R$之间的边构成一个匹配，即$B$中的每个顶点至多与$R$中的一个邻居相连，反之亦然。 如果对于某个整数$d\geq 1$，我们允许$B$中的每个邻居最多与$R$中的$d$个邻居相连，反之亦然，我们就得到了更一般化的$d$-Cut 问题。 已知对于每个$d\geq 1$，$d$-Cut 是 NP 完全问题。 然而，对于爪-free图，仅知道对于$d=1$，$d$-Cut问题是多项式时间可解的，而对于$d\geq 3$则是NP完全的。 我们通过证明NP完全性解决了缺失的情况$d=2$。 这源于我们的更一般的研究，在这项研究中我们也限制了最大度数。 也就是说，我们证明了对于每个$d\geq 2$,$d$-Cut，在最大度为$p$的无爪图上受到限制时，如果$p\leq 2d+1$则可以在常数时间内求解，而如果$p\geq 2d+3$则是 NP 完全的。 此外，在前一种情况下，我们可以在线性时间内找到一个$d$-Cut。 我们还展示了我们的爪形图正结果如何可以推广到$S_{1^t,l}$-自由图中，其中$S_{1^t,l}$是从一个具有$t+2$个顶点的星形图通过将其一条边恰好细分$l$次得到的图。 显示英文摘要

摘要： The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets $B$ and $R$ such that the edges between $B$ and $R$ form a matching, that is, every vertex in $B$ has at most one neighbour in $R$, and vice versa. If for some integer $d\geq 1$, we allow every neighbour in $B$ to have at most $d$ neighbours in $R$, and vice versa, we obtain the more general problem $d$-Cut. It is known that $d$-Cut is NP-complete for every $d\geq 1$. However, for claw-free graphs, it is only known that $d$-Cut is polynomial-time solvable for $d=1$ and NP-complete for $d\geq 3$. We resolve the missing case $d=2$ by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every $d\geq 2$, $d$-Cut, restricted to claw-free graphs of maximum degree $p$, is constant-time solvable if $p\leq 2d+1$ and NP-complete if $p\geq 2d+3$. Moreover, in the former case, we can find a $d$-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to $S_{1^t,l}$-free graphs where $S_{1^t,l}$ is the graph obtained from a star on $t+2$ vertices by subdividing one of its edges exactly $l$ times.