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

doi:10.3778/j.issn.1002-8331.1703-0356

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

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

刘维婵，张欣

西安电子科技大学数学与统计学院，西安 710071

出版日期:2018-05-15 发布日期:2018-05-28

Equitable vertex arboricity of outer-1-planar graphs

LIU Weichan, ZHANG Xin

School of Mathematics and Statistics, Xidian University, Xi’an 710071, China

Online:2018-05-15 Published:2018-05-28

摘要/Abstract

摘要： 图的均匀树[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

刘维婵，张欣. 外1-平面图的均匀点荫度[J]. 计算机工程与应用, 2018, 54(10): 51-53.

LIU Weichan, ZHANG Xin. Equitable vertex arboricity of outer-1-planar graphs[J]. Computer Engineering and Applications, 2018, 54(10): 51-53.

[1]	孟芸，胡欣，代亮，余雷. 干扰车载网络中增强连通性的资源分配算法[J]. 计算机工程与应用, 2019, 55(7): 9-15.
[2]	李艳，张欣. 外1-平面图的均匀边染色[J]. 计算机工程与应用, 2019, 55(24): 37-40.
[3]	刘康1，张雪英1，李凤莲1，田玉楚1，2. 基于通信负载均衡的社交网络图分割方法[J]. 计算机工程与应用, 2018, 54(4): 66-71.
[4]	宫辰，武丽芳，刘维婵，张欣. 不含特殊子式的符号图的选择数[J]. 计算机工程与应用, 2018, 54(16): 55-58.
[5]	陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍. 图论中最大独立集问题的精确算法[J]. 计算机工程与应用, 2016, 52(1): 20-22.
[6]	郑艳1，徐国军2，覃锡忠1，贾振红1. 均衡满意度的并行单色连通分支频谱分配算法[J]. 计算机工程与应用, 2014, 50(18): 197-201.
[7]	卢进军1，龙英艳2，潘宏利1. 基于演化图论的可靠的VANETs路由协议[J]. 计算机工程与应用, 2014, 50(13): 96-102.
[8]	张晗1，何东健2. 一种融合纹理信息与图论的图像分割方法[J]. 计算机工程与应用, 2014, 50(1): 180-184.
[9]	韩中1，2，赵升吨2，张贵成2，3，阮卫平3，李建平3，沈红立3. 流程制造系统辨识的自动结构性建模方法[J]. 计算机工程与应用, 2014, 50(1): 227-231.
[10]	曹敦，陈子琦. 一种新的无线传感器网络节点定位算法[J]. 计算机工程与应用, 2012, 48(8): 116-118.
[11]	陈善超，符红光，王颖. 改进的一种图论分割方法在舌像分割中的应用[J]. 计算机工程与应用, 2012, 48(5): 201-203.
[12]	许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.
[13]	应德全¹,应晓敏²,叶继华¹. 一种基于图论的聚类算法NeiMu[J]. 计算机工程与应用, 2009, 45(3): 47-50.
[14]	王凤¹，林杰^1，2. 高校排课问题的图论模型及算法[J]. 计算机工程与应用, 2009, 45(27): 240-242.
[15]	李珂^1，3，连一峰^1，2，3. 一种面向DDoS攻击的网络安全态势评估方法[J]. 计算机工程与应用, 2009, 45(27): 88-91.

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

Equitable vertex arboricity of outer-1-planar graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics