关于2-边连通3正则图荫度的一个注（英文）  

A Note on Arboricity of 2-edge-connected Cubic Graphs

作　　者：郝荣霞[1] 赖虹建[2,3] 刘浩洋[4] 

机构地区：[1]北京交通大学数学系,北京100044 [2]新疆大学数学与系统科学学院,乌鲁木齐新疆830046 [3]西弗吉尼亚大学数学系 [4]北京大学数学科学学院,北京100871

出　　处：《数学进展》2015年第6期865-870,共6页Advances in Mathematics（China）

基　　金：Supported by NSFC(No.11371052,No.11171020,No.11271012)

摘　　要：图G的点荫度a(G)是G的使得每个子集诱导一个森林的顶点划分中子集的最少个数.我们熟知对任何平面图G,a(G)≤3,且对任何直径最大是2的平面图有a(G)≤2.文献[European J.Combin.,2008,29(4):1064-1075]中给出下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.本文证明了任何2-边连通上可嵌入的3-正则图G(G≠K_4)都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.The vertex-arboricity a（G） of a graph G is the minimum number of subsets into which the set of vertices of G can be partitioned so that each subset induces a forest. It is well known that a（G） ≤ 3 for any planar graph G, and that a（G） ≤ 2 for any planar graph G of diameter at most 2. The conjecture that every planar graph G without 3-cycles has a vertex partition （V1, V2） such that V1 is an independent set and V2 induces a forest was given in [European J. Corabin., 2008, 29（4）： 1064-1075]. In this paper, we prove that a 2-edge-connected cubic graph which satisfies some condition has this partition. As a corollary, we get the result that every up-embeddable 2-edge-connected cubic graph G（G≠K4） has a vertex partition （V1, V2） such that V1 is an independent set and V2 induces a forest.

关 键 词：边连通度 诱导森林 荫度 

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