一个非平凡图G的点荫度a(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展,例如,随机图的点荫度以分式点荫度等.得到一个关于平面图的点荫度的一个上界;如果平面图G是没有3-圈,或是没有4-圈,或是没有5-圈,那么G的点荫度不超过2.研究的起因是一个著名的猜想:任何3-可着色的平面图的点荫度不超过2.四色定理是图论中最著名的一个定理,伴随产生了一个问题,那就是什么样的平面图是3-可着色的.不幸,这是一个难问题,Garey等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题.因此这个猜想是一个不易解决的,人们开始在一些特殊图上进行验证这个猜想是否正确.我们知道一个著名的定理:不含3-圈的平面图是3-可着色的.结合结果,给出猜想的一个正面的肯定.Havel给出两个反例,如果平面图含有4-圈或有5-圈是不可3-可着色的,因此4-圈和5-圈在证明平面图是3-可着色时必须排除.不过在结论中,如果平面图不含有4-圈或不含有5-圈,那么它的点荫度不超过2.从而可以看出猜想的条件还是很强的.同时我们的结果也拓宽了张忠辅等人的结果:外平图的点荫度不超过2.
The vertex arboricity a(G) of a nonempty graph G is the minimum number of subsets into which the vertex set V (G) can be partitioned so that each subset induces a subgraph that is a forest. The research on the vertex arboricity of a graph G becomes a focus field as well as many extended branches on the graph theory in the past years, such as the vertex arboticity on random graph and fractional arboricity etc. This paper provides an upper bound for a(G) of a connected nonempty plane graph G, namely a(G) 42 where G is a plane graph without/-cycles for some i∈{3, 4, 5}. The work is concerned with a famous conjecture which says that every 3-colorable plane graph has the vertex arboricity which is no more than 2. The famous 4-coloring theorem produces a new problem: what kind of plane graphs is 3- colorable. But this problem is NP-hard even for a given plane graph with a degree not exceeding 4 is 3-colorable or not (Garey et al , 1976, Theoretical Computer Science, 1:237-267). So the conjecture is hard to solve. Therefore, people have to find some special graphs to identify the conjecture. It is well known that every triangle-free plane graph is 3-colorable. Thus, the conjecture holds if G is a plane graph with triangle-free. In Havel (1969, Journal of Combinatorial Theory, 7:184-186), Havel provided that both 4-cycles and 5-cycles must be excluded to ensure that the plane graphs are 3-colorable. But in our theorem, if a plane graph G is either 4-cycle-free or 5-cycle-free, then a(G) ≤2. The conjecture's condition is stronger. And our results improve the conclusion on a(G) ≤ 2 for outer plane graph(Zhang and Wang , 1991, Mathematical Applicata, 4(2) : 14-18).