论文标题
关于有界半径和$ h $的图形的匹配剪切的复杂性
On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs
论文作者
论文摘要
对于连接的图形$ g =（v，e）$，如果断开$ g-m $，则匹配的$ m \ subseteq e $是$ g $的匹配切割。众所周知，对于整数$ d $，相应的决策问题匹配切割是可溶解的，对于直径图的多项式时间可解决，如果$ d \ leq 2 $，则最多可解决$ d $，如果$ d \ d \ geq 3 $，则可以解决。对于有界半径的图，我们证明了相同的二分法。对于图$ h $，如果不包含$ h $作为诱导子图，则图形为$ h $ free。由于我们的结果，我们可以以$ p_6 $ free图的方式解决多项式时间的匹配剪辑，从而扩展了Feghali的最新结果，以$ p_5 $ - free-free图。然后，我们将结果扩展到以$（SP_3+P_6）$ - 每$ s \ geq 0 $的免费图表，并启动以$ h $ free Graphs的匹配切割的复杂性分类。
For a connected graph $G=(V,E)$, a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most $d$ if $d\leq 2$ and NP-complete if $d\geq 3$. We prove the same dichotomy for graphs of bounded radius. For a graph $H$, a graph is $H$-free if it does not contain $H$ as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for $P_6$-free graphs, extending a recent result of Feghali for $P_5$-free graphs. We then extend our result to hold even for $(sP_3+P_6)$-free graphs for every $s\geq 0$ and initiate a complexity classification of Matching Cut for $H$-free graphs.
