Equitable vertex arboricity of outer-1-planar graphs

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

Abstract

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

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

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

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

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

[1]	MENG Yun, HU Xin, DAI Liang, YU Lei. Connectivity Improvement Resource Allocation Algorithm in Interference Vehicular Networks [J]. Computer Engineering and Applications, 2019, 55(7): 9-15.
[2]	LI Yan, ZHANG Xin. Equitable Edge Coloring of Outer-1-Planar Graphs [J]. Computer Engineering and Applications, 2019, 55(24): 37-40.
[3]	LIU Kang1, ZHANG Xueying1, LI Fenglian1, TIAN Yuchu1，2. Graph partitioning method for social networks based on communication load balancing [J]. Computer Engineering and Applications, 2018, 54(4): 66-71.
[4]	GONG Chen, WU Lifang, LIU Weichan, ZHANG Xin. Choosability of signed graphs without certain minors [J]. Computer Engineering and Applications, 2018, 54(16): 55-58.
[5]	CHEN Jizhen, NING Aibing, ZHI Zhibing, HU Linlin, ZHANG Huizhen. Exact algorithm for maximum independent set problem in graph theory [J]. Computer Engineering and Applications, 2016, 52(1): 20-22.
[6]	ZHANG Han1, HE Dongjian2. Image segmentation approach by combining texture information and graph theory [J]. Computer Engineering and Applications, 2014, 50(1): 180-184.
[7]	HAN Zhong1，2, ZHAO Shengdun2, ZHANG Guicheng2，3, RUAN Weiping3, LI Jianping3, SHEN Hongli3. Automatic structural modeling method based on process manufacturing system identifications [J]. Computer Engineering and Applications, 2014, 50(1): 227-231.
[8]	CAO Dun, CHEN Ziqi. New localization algorithm for wireless sensor networks [J]. Computer Engineering and Applications, 2012, 48(8): 116-118.
[9]	CHEN Shanchao, FU Hongguang, WANG Ying. Application of improved graph theory image segmentation algorithm in tongue image segmentation [J]. Computer Engineering and Applications, 2012, 48(5): 201-203.
[10]	LAN Meihui1，XU Jian1，SUN Yu2. Ontology similarity computation based on spectral graph theory [J]. Computer Engineering and Applications, 2011, 47(28): 110-112.
[11]	YANG Jinglin，WANG Chengru. Adaptive texture image retrieval based on spectral graph theory [J]. Computer Engineering and Applications, 2011, 47(22): 195-197.
[12]	WANG Huiqing，CHEN Junjie，GUO Kai. Research of spectral clustering based on genetic algorithm [J]. Computer Engineering and Applications, 2011, 47(14): 143-145.
[13]	XU Jin-xing，WU Su-ping. Approximate algorithm for traveling salesman problem based on graph theory [J]. Computer Engineering and Applications, 2009, 45(32): 51-52.
[14]	YING De-quan¹,YING Xiao-min²,YE Ji-hua¹. NeiMu：novel clustering algorithm based on graph theory [J]. Computer Engineering and Applications, 2009, 45(3): 47-50.
[15]	LI Ke^1，3，LIAN Yi-feng^1，2，3. Method of network security situation assessment under DDoS attacks [J]. Computer Engineering and Applications, 2009, 45(27): 88-91.

Equitable vertex arboricity of outer-1-planar graphs

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics