论文标题
完美的匹配切割将图表分配到互补子图中
Perfect matching cuts partitioning a graph into complementary subgraphs
论文作者
论文摘要
为了分配为补充子图（comp-sub），我们获得了一个图$ g =（v，e）$和一个边缘设置属性$π$，并询问是否可以将$ g $分解为两个图，$ h $及其补充$ \ overline {h yline {h} $，以某种方式$ h $，以某种方式，以使得$ h $，以使$ cut $ cut $ cut $ cut $ [v（v v（v v（h），v（h），v（h），v（h），v（h），v（h）， $π$。在先前的工作中，我们考虑comp-sub（$π$）当属性$π= \ nathcal {pm} $指定分解的边缘切割是完美的匹配时。我们证明，当Graph $ G $为$ \ {C_ {K \ GEQ 7}，\ OVERLINE {C} _ {K \ geq 7} \ efree时，Comp-Sub（$ \ MATHCAL {PM} $）是GI-HARD。另一方面，我们表明Comp-Sub（$ \ Mathcal {pm} $）在$ hole $ - Free Graphs和$ p_5 $ - Free Graphs上是多项式时间的求解。此外，我们介绍了conder，远程遗传和扩展的$ p_4 $ -laden图的Comp-Sub（$ \ Mathcal {pm} $）的特征。
In Partition Into Complementary Subgraphs (Comp-Sub) we are given a graph $G=(V,E)$, and an edge set property $Π$, and asked whether $G$ can be decomposed into two graphs, $H$ and its complement $\overline{H}$, for some graph $H$, in such a way that the edge cut $[V(H),V(\overline{H})]$ satisfies the property $Π$. Motivated by previous work, we consider Comp-Sub($Π$) when the property $Π=\mathcal{PM}$ specifies that the edge cut of the decomposition is a perfect matching. We prove that Comp-Sub($\mathcal{PM}$) is GI-hard when the graph $G$ is $\{C_{k\geq 7}, \overline{C}_{k\geq 7} \}$-free. On the other hand, we show that Comp-Sub($\mathcal{PM}$) is polynomial-time solvable on $hole$-free graphs and on $P_5$-free graphs. Furthermore, we present characterizations of Comp-Sub($\mathcal{PM}$) on chordal, distance-hereditary, and extended $P_4$-laden graphs.
