不含相邻短圈的平面图的点荫度问题

Vertex Arboricity Problem of Planar Graphs without Adjacent Short Cycles

摘要: 在社团网络的研究中，社团结构划分一直是一个有价值的研究课题。 出于安全考虑，对一个新的社团结构划分问题进行研究，它可以在图论中转化为最小化问题。 图G的点荫度是对G的点集进行顶点着色，使得每个颜色类的导出子图是G 的森林的最小颜色数，一般用符号va(G)表示。 一般地，对于任意平面图 G ，va(G) ≤ 3，且对任意非空图 G，va(G) ≥ 1 成立。 显然，va(G) = 1当且仅当图G 是一个无圈图。 对于某些特殊情况，如果图G是一个不含3-圈的平面图，va(G) ≤ 2。Raspaud 和Wang 等人证明了如果图G是一个不含4-圈或不含5-圈的平面图，则va(G) ≤ 2。 此外，Huang, Shui 和Wang 等人证明了如果图G是一个不含7-圈的平面图，则va(G) ≤ 2。 在本文中，我们证明了如果图G是一个不含相邻的3-圈和4-圈的平面图，或者不含相邻的4-圈和5-圈的平 面图，则va(G) ≤ 2。

Abstract: In the research of social networks, social structure decomposition has always been a valuable research topic. For security reasons, we study a new social structure decomposition problem, which can be decomposed into a problem of minimization in graph theory. The vertex arboricity of a graph G, denoted by va(G), is the minimum number of subsets such that the vertices of G can be colored and every color class induces an acyclic graph such as a forest of G. Normally, va(G) ≤ 3 for every planar graph G and va(G) ≥ 1 for every nonempty graph G. There is no doubt that va(G) = 1 if and only if G is an acyclic graph. For some special cases, it is known that va(G) ≤ 2 if G is a planar graph without 3-cycles. Recently, Raspaud and Wang et al.  proved that va(G) ≤ 2 if G is a planar graph without 4-cycles or without 5-cycles. In addition, Huang, Shiu, and Wang showed that if G is a planar graph without 7-cycles, then va(G) ≤ 2. In this paper, we prove that if G is a planar graph without adjacent 3-cycles and 5-cycles, or without adjacent 4-cycles and 5-cycles, then va(G) ≤ 2.