关于曲面的列表点荫度定义与探讨  

Definition and Discussion of the List Point Arboricity of Graphs on Surfaces

作　　者：薛妮妮[1] 严志丹[1] 

机构地区：[1]塔里木大学信息工程学院,新疆阿拉尔843300

出　　处：《塔里木大学学报》2010年第1期47-48,共2页Journal of Tarim University

摘　　要：设为一图,用最少的颜色去着图,使得每种颜色的导出图是森林的所需色数,称为点荫度,记为。在这篇文章中,定义了列表点荫度,利用欧拉公式、面度和与点度和相等及亏格与顶点数的关系得到了亏格为的图的列表点荫度的上界及无三圈的亏格为的图的列表点荫度的上界。Let G be a graph. The point arboricity of G, denoted by p, is the minimum number of colors that can be used to color the ver- tices of G so that each color class induces an acyclic subgraph of G. In this paper, we define the list version of point arboricity of G, denoted by p~. We determine the upper bound of list point arboricity of G with genus g and triangle - free graphs, by Euler formula, the equality between sum of face degree and sum of vertex degree, and the relation between genus g and vertex number n .

关 键 词：点荫度 列表点荫度 亏格 

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