关于3-正则图的消圈数和点荫度的一个注记（英文）  

A Note on Decycling Number and Vertex-arboricity of Cubic Graphs

作　　者：杨超 任韩[2,3] YANG Chao;REN Han(School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science,Shanghai, 201620, P. R. China;Department of Mathematics, East China Normal University, Shanghai,200241, P? R? China;Shanghai Key Laboratory of Pure Mathematics and Mathematical Practice,Shanghai, 200241, P. R. China)

机构地区：[1]上海工程技术大学数理与统计学院,上海,201620 [2]华东师范大学数学系,上海,200241 [3]上海市核心数学与实践重点实验室,上海,200241

出　　处：《数学进展》2019年第4期504-508,共5页Advances in Mathematics（China）

基　　金：NSFC(Nos.11171114,11401576,11533004);Science and Technology Commission of Shanghai Municipality(No.13dz2260400)

摘　　要：本文从图的嵌入角度考虑,给出了一个计算3-正则图的消圈数(见[J.Graph Theory,1997,25(1):59-77])的新公式.结合所得消圈数公式和Xuong的最大亏格定理(见[J.Combin.Theory Ser.B,1979,26(2):217-225]),进而得到了3-正则图的点荫度为2,此结果证明了Raspaud和王维凡在文献[European J.Combin.,2008,29(4):1064-1075]中给出的下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V1,V2)使得V1是独立集,V2诱导一个森林.In this paper,from the view of graph embeddings,we provide a formula for the decycling number(see[J.Graph Theory,1997,25(1):59-77])of cubic graphs.Together with the above formula and Xuong’s maximum genus theorem(see[J.Combin.Theory Ser.B,1979,26(2):217-225]),we prove that a(G)= 2 for any cubic graph G,where a(G)is the vertex-arboricity of G,and the result confirms the conjecture "every planar graph G without3-cycles has a vertex partition(V1,V2)such that V1 is an independent set and V2 induces a forest" due to Raspaud and Wang[European J.Combin.,2008,29(4):1064-1075].

关 键 词：消圈数 点荫度 Brooks定理 3-正则图 

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