论文标题
完美匹配切割问题的复杂性
The complexity of the Perfect Matching-Cut problem
论文作者
论文摘要
完美的匹配切割是确定图形是否具有包含边缘切割的完美匹配的问题。我们表明，对于具有最高度的平面图的平面图，对于具有腰围五的平面图，对于双分部分的五型图，对于直径三的图和直径四的双分部分图。我们表明，以下图的类别存在多项式时间算法：无爪，$ p_5 $ - free，直径二，二分，直径为三和具有界树宽度的图形。
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.
