嵌入曲面的图的点荫度  

On the vertex-arboricity of embedded graphs

作　　者：孙林[1] 蔡华[2] 

机构地区：[1]昌吉学院数学系,新疆昌吉831100 [2]山东大学数学学院,山东济南250100

出　　处：《山东大学学报（理学版）》2015年第2期38-42,54,共6页Journal of Shandong University(Natural Science)

基　　金：新疆维吾尔自治区高等学校科研计划项目(XJEDU2014S067)

摘　　要：图G的导出森林k-划分是指其顶点集V(G)的一个k-划分(V1,V2,…,Vk),使得对于每个i(1≤i≤k),导出子图G[Vi]是一个森林。图G的点荫度是使得图G有导出森林k-划分的最小的正整数k,记为va(G)。主要证明了如果图G能够嵌入到欧拉示性数非负的曲面上,则当图G满足三类条件时,可以得到va(G)≤2。An induced forest k-partition of a graph G is a k-partition（ V1,V2,…,Vk） of the vertex set V（ G） such that,for each i with 1≤i≤k,the induced subgraph G[Vi]is a forest. The vertex arboricity of a graph G is the minimum positive integer k such that G has an induced forest k-partition,denoted by va（ G）. Let G be a simple graph embedded in a surface of nonnegative Euler characteristic,and if G satisfies three kinds of conditions,then va（ G） ≤2.

关 键 词：点荫度 放电法 距离 

分 类 号：O157.5[理学—数学]