图的强均匀点荫度

Strong Equitable Vertex Arboricity of Graphs

摘要: 图G的均匀k-划分是将图G的顶点划分，使得每个划分类导出的子图是一个森林且任意两个划分类中的顶点数最多相差1。图G的强均匀点荫度是最小整数k，使得对任意的$k^{\prime }\ge k$ ，图G都有一个均匀$k^{\prime }$ -划分。本文证明每个无割点的外平面图G，它的强均匀点荫度至多为，继而证明了无割点的外平面图满足猜想：对任何平面图G，强均匀点荫度至多是。同时，得到平方图的强均匀点荫度的下界为$\lceil \frac{\Delta +1}{2}\rceil$ ，证明圈$C_n$ 的平方图在$n=5$ 时，强均匀点荫度为3，当$n\ne 5$ 时，强均匀点荫度为2，从而证明圈的平方图满足强均匀点荫的猜想。

Abstract: An equitable k-partition of a graph G is a partition of the vertex set of G such that the subgraph induced by each partition class is a forest and the sizes of any two parts differ by at most one. The strong equitable vertex arboricity of G is the minimum integer k so that G has an equitably $k^{\prime }$ - partitioned for an $k^{\prime }\ge k$ . This paper proves that the strong equitable vertex arboricity of each outerplanar has no cut-vertices G is at most 2, and then proves that the outerplanar satisfies the conjecture that for any plan G, the strong equitable vertex arboricity is at most 3. Meanwhile, the lower bound of the strong equitable vertex arboricity of the square graph is $\lceil \frac{\Delta +1}{2}\rceil$ , which proved that the square graph of the circuits $C_n$ is 3 when $n=5$ , and the strong equitable vertex arboricity is 2 when $n\ne 5$ , so that the square graph of the circuits satisfies the conjecture of strong equitable vertex arboricity.