图的导出森林2－划分

Partition a Graph into Two Induced Forests

对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．

Is there a 2-partiton (V1,V2) of V(G) for a given simplc graph G such that each induced subgraph G[Vi] is a forest? ms problem is called induced forest 2-partition problem. This paper shows that this problem is NP-complete for graphs with maximum degree 5, and polynomially solvable for graphs with maximum degree at most 4.