您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (12): 127-129.doi: 10.6040/j.issn.1671-9352.0.2014.479

• 论文 • 上一篇    下一篇

3-正则Halin图的完备染色

孟宪勇1, 郭建华2, 苏本堂1   

  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

PDF (PC)

929

摘要： 研究了3-正则(或立方)Halin图的完备染色,针对非轮图的3-正则Halin图,提出了一种具体的完备染色,简单确定了非轮图(Wn)的3-正则Halin图的完备色数是6,且使得3-正则Halin图的完备染色可用计算机实现。

关键词: 平面图, Halin图, 完备色数, 完备染色

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.

Key words: planar graph, Halin graph, complete coloring, complete chromatic number

中图分类号: 

  • 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] 李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[2] 谭香. 一类最大度为6的平面图的全染色[J]. 《山东大学学报(理学版)》, 2021, 56(11): 71-75.
[3] 刘卓雅,徐常青. 无相交三角形平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2020, 55(9): 36-41.
[4] 陈宏宇,钟斌. 不含相交5-圈的平面图的线性2-荫度[J]. 《山东大学学报(理学版)》, 2020, 55(7): 38-45.
[5] 刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[6] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[7] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[8] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[9] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[10] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[11] 宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 65-67.
[12] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[13] 孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13.
[14] 马刚. 围长不小于11且最大度为3的平面图的#br# 无圈列表边染色[J]. 山东大学学报（理学版）, 2014, 49(2): 18-23.
[15] 陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26-30.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发