外1-平面图的均匀点荫度  

Equitable vertex arboricity of outer-1-planar graphs

作　　者：刘维婵 张欣 LIU Weichan;ZHANG Xin(School of Mathematics and Statistics,Xidian University,Xi’an 710071,China)

机构地区：[1]西安电子科技大学数学与统计学院,西安710071

出　　处：《计算机工程与应用》2018年第10期51-53,80,共4页Computer Engineering and Applications

基　　金：高等学校博士学科点专项科研基金新教师类项目(No.20130203120021);国家自然科学基金青年科学基金项目(No.11301410);陕西省自然科学基础研究计划面上基金项目(No.2017JM1010);中央高校基本科研业务费项目(No.JB170706)

摘　　要：图的均匀树k-染色是图的一个点k-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图G具有均匀树k-染色的最小整数k称为图G的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。An equitable tree-k-coloring is a vertex k-coloring.The sizes of any two color classes differ by at most 1,and the subgraph induced by any color class is a forest.The minimum integer k that a graph G admits an equitable tree-k-coloring is the equitable vertex arboricity of G.It is proven that the equitable vertex arboricity of every outer-1-planar graph is at most 3,and then the equitable vertex arboricity conjecture is verified for outer-1-planar graphs.

关 键 词：图论 外1-平面图 均匀染色 点荫度 

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