• 论文 •

### 3-正则Halin图的完备染色

1. 1. 山东农业大学信息科学与工程学院, 山东 泰安 271038;
2. 东北师范大学数学与统计学院, 应用统计教育部重点实验室, 吉林 长春 130024
• 收稿日期:2014-11-04 修回日期:2015-11-18 出版日期:2015-12-20 发布日期:2015-12-23
• 作者简介:孟宪勇(1972-),男,博士,副教授,研究方向为图模型、数据科学.E-mail:xym@sdau.edu.cn
• 基金资助:
全国统计科学研究计划项目课题(2012ZY137);山东农业大学青年创新基金(23289)

### The complete coloring of 3-regular Halin graphs

MENG Xian-yong1, GUO Jian-hua2, SU Ben-tang1

1. 1. College of Information Science and Engineering, Shandong Agricultural University, Taian 271038, Shandong, China;
2. Key Laboratory for Applied Statistics of MOE and School of Mathematics and Statistics, Northeast Normal University, Changchun 130024, Jilin, China
• Received:2014-11-04 Revised:2015-11-18 Online:2015-12-20 Published:2015-12-23

Abstract: The complete coloring of 3-regular Halin graphs is studied. A procedure, for completely coloring an 3-regular Halin graph which is not a wheel graph, is proposed. By this procedure, the conclusion that χC(G)=6, where G(≠W4) is a 3-regular Halin graph, can be easily obtained. Furthermore, this implies that the complete coloring of a 3-regular Halin graph can be solved by computer.

• O157
 [1] BONDY J A, MURTY U S R. Graph theory with application[M]. New York: Macmillan, 1976. [2] HALIN R. Studies on minimally n-connected graphs[J]. Combinatorial Mathematics and its Applications, 1971: 129-136. [3] KRONK H V, MITCHEM J. A seven-color theorem on the sphere[J]. Discrete Math, 1971, 5:253-260. [4] BORODIN O V. Consistnet coloring of graphs on the sphere[J]. Metody Diskner Analyza, 1987, 45:21-27. [5] ZHANG Zhongfu, WANG Jianfang, WANG Weifan, et al. The complete chromatic number of some planar graphs[J]. Science in China: Ser A, 1993(10):1169-1177. [6] 吴建良. 外平面图的完备染色[J]. 山东矿业学院学报,1996, 2: 220-222. WU Jianliang. The entire coloring of outerplanar graphs[J]. Journal of Shandong Mining Institute, 1996, 2:220-222. [7] 刘林忠, 张忠辅, 王建方. 最大度不小于6 的伪-Halin图的完备色数[J].数学研究与评论,2002, 22:663-668. LIU Linzhong, ZHANG Zhongfu, WANG Jianfang. On the complete chromatic number of pseudo-Halin graphs with Δ(G)≥6[J]. Journal of Mathematical Research and Exposition, 2002, 22:663-668. [8] 姚明,姚兵,陈祥恩. 立方Halin图的完备色数[J].山东大学学报:理学版,2012, 47(2):65-70. YAO Ming, YAO Bing, CHEN Xiang'en. On complete chromatic numbers of cubic Halin graphs[J]. Journal of Shandong University: Natural Science, 2012, 47(2):65-70.
 [1] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41. [2] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106. [3] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39. [4] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41. [5] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78. [6] 宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 65-67. [7] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101. [8] 孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13. [9] 马刚. 围长不小于11且最大度为3的平面图的#br# 无圈列表边染色[J]. 山东大学学报（理学版）, 2014, 49(2): 18-23. [10] 陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26-30. [11] 张佳丽,苗连英,宋文耀. 最大度为8不含相邻4-圈的1-平面图边色数[J]. 山东大学学报（理学版）, 2014, 49(04): 18-23. [12] 徐常青1,安丽莎1,杜亚涛2. 平面图线性2-荫度的一个上界[J]. 山东大学学报（理学版）, 2014, 49(04): 38-40. [13] 朱海洋1,陈伟1,吕新忠2,李培君3. 无4,5,6-圈且无两个相交三角形的平面图的L(p,q)-标号[J]. J4, 2013, 48(4): 28-34. [14] 薛玲1, 吴建良2*. 较少短圈的平面图的全色数[J]. J4, 2012, 47(9): 84-87. [15] 王苒群,左连翠. 不含4-圈和5-圈的平面图的线性2-荫度[J]. J4, 2012, 47(6): 71-75.
Viewed
Full text

Abstract

Cited

Shared
Discussed