图的点线荫度(英文)

The Vertex Linear Arboricity of a Graph

图G的顶点集V(G)划分为一些子集,使得每个子集的导出子图是0线森林(即每个分支是路)的最小子集数叫图G的点线荫度,记为v|a(G).Poh K S证明了任何平面图的点线荫度最多是3.Matsumato M给出了图的点线荫度的上界,即v|a(G)≤[△(G)/2].这里△(G)是G的最大度.本文给出了完全n部图的点线荫度计算公式,同时也给出了任意图的点线荫度的精确上下界．

: The vertex linear arboricity of a graph G, denoted by v|a(G), is the minimumnumber of sets into which the vertices set V(G) can be partitioned so that each set induce a linearforest whose eacli compehent is a path. Poh K S showed that the vertex linear arboricity of any pla-nar graph is at most 3. Matsumoto M provides the upper bound for the vertex linear arboricity ofa graph G,namely,v|a(G)≤1+ [△(G)/2], where△ (G) denotes maximum degree of G. In thispaper.we give a formula for the vertex linear arboricity of a complete n-partite graph. This paperprovides also a sharp upper bound for the vertex linear arboricity,together with a lower bound.