计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (10): 51-53.DOI: 10.3778/j.issn.1002-8331.1703-0356

• 理论与研发 • 上一篇    下一篇

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

刘维婵,张  欣   

  1. 西安电子科技大学 数学与统计学院,西安 710071
  • 出版日期:2018-05-15 发布日期:2018-05-28

Equitable vertex arboricity of outer-1-planar graphs

LIU Weichan, ZHANG Xin   

  1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China
  • Online:2018-05-15 Published:2018-05-28

摘要: 图的均匀树[k]-染色是图的一个点[k]-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图[G]具有均匀树[k]-染色的最小整数[k]称为图[G]的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。

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

Abstract: 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.

Key words: graph theory, outer-1-planar graph, equitable coloring, vertex arboricity