JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (12): 127-129.doi: 10.6040/j.issn.1671-9352.0.2014.479

Previous Articles     Next Articles

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)

628

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

CLC 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] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41.
[2] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.
[3] WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39.
[4] CHEN Hong-yu, ZHANG Li. Linear 2-arboricity of planar graphs with 4-cycles have no common vertex [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 36-41.
[5] TAN Xiang. Total colorings of planar graphs without 6-cycles and adjacent 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 72-78.
[6] SONG Hong-jie, GONG Xiang-nan, PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing total coloring of Halin graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 65-67.
[7] ZHU Hai-yang, GU Yu, LÜ Xin-zhong. New upper bound on the chromatic number of the square of a planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(2): 94-101.
[8] MA Gang. Acyclic list edge coloring of planar graphs with girth #br# ≥ 11 and maximum degree 3 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(2): 18-23.
[9] CHEN Hong-yu1, ZHANG Li2. The linear 2-arboricity of planar graphs without 5-, 6-cycles with chord [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 26-30.
[10] ZHANG Jia-li, MIAO Lian-ying, SONG Wen-yao. Edge colorings of 1-planar graphs for maximum degree eight #br# without adjacent 4-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(04): 18-23.
[11] XU Chang-qing1, AN Li-sha1, DU Ya-tao2. An upper bound on the linear 2-arboricity of planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(04): 38-40.
[12] ZHU Hai-yang1, CHEN Wei1, L Xin-zhong2, LI Pei-jun3. On L(p,q)-labeling of planar graphs without 4,5,6-cycles and intersecting triangles [J]. J4, 2013, 48(4): 28-34.
[13] XUE Ling1, WU Jian-liang2*. Total chromatic number of planar graphs with few short cycles [J]. J4, 2012, 47(9): 84-87.
[14] DING Wei. Acyclic edge coloring of planar graphs without 4-Cycles [J]. J4, 2012, 47(6): 76-79.
[15] HAN Qiang1, HU Yi-hong2. Research of the reasonable orientation of a solid urban transportation network [J]. J4, 2012, 47(3): 67-70.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd