JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2016, Vol. 51 ›› Issue (2): 94-101.doi: 10.6040/j.issn.1671-9352.0.2014.594

Previous Articles     Next Articles

New upper bound on the chromatic number of the square of a planar graph

ZHU Hai-yang1, GU Yu1, LÜ Xin-zhong2   

  1. 1. Department of Flight Support Command, Air Force Logistics College, Xuzhou 221000, Jiangsu, China;
    2. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
  • Received:2014-12-31 Online:2016-02-16 Published:2016-03-11

PDF (PC)

1048

Abstract: Let V(G), E(G), Δ(G) and χ(G) denote the vertex set, the edge set, the maximum degree and the chromatic number of a graph G, respectively. The square G2 of a graph G is defined such that V(G2)=V(G), and uv∈E(G2)if and only if 1≤dG(u,v)≤2. It is proved that χ(G2)≤Δ(G)+8 if G is a planar graph with Δ(G)≤6 and girth g(G)≥5.

Key words: planar graph, girth, coloring, squares

CLC Number: 

  • O157.5
[1] 徐俊明. 图论及其应用[M]. 2版. 合肥: 中国科学技术大学出版社, 2005. XU Junming. Graph theory and its applications[M]. 2nd ed. Hefei: China University of Science and Technology Press, 2005.
[2] WEGNER G. Graphs with given diameter and coloring problem[R]. Dortmund, Germany:Technical Report, University of Dortmund, 1977.
[3] HEUVEL J V, McGUINESS S. Coloring of the square of a planar graph[J]. J Graph Theory, 2003, 42:110-124.
[4] MOLLY M, SALAVATIPOUR M R. A bound on the chromatic number of the square of a planar graph[J]. J Combinatorial Theory: B, 2005, 94:189-213.
[5] WANG Weifan, CAI L Z. Labeling planar graphs without 4-cycles with a conditionon distance two[J]. J Discrete Applied Mathematics, 2008, 156:2241-2249.
[6] ZHU Haiyang, HOU Lifeng, CHEN Wei, et al. The L(p; q)-labelling of planar graphs without 4-cycles[J]. Discrete Applied Mathematics, 2014, 162:355-363.
[7] BORODIN O V, IVANOVA A O. 2-distance Δ+2-coloring of planar graphs with girth six and Δ(G)≥18[J]. Discrete Mathematics, 2009, 309:6496-6502.
[8] WANG Weifan, LIH K W. Labeling planar graphs with conditions on girth and distance two[J]. SIAM J Discrete Mathematics, 2003, 17(2):264-275.
[9] CHARPENTIER C, MONTASSIER M, RASPAUD A. L(p,q)-labeling of sparse graphs[J]. Journal of Combinatorial Optimization, 2013, 25(4):646-660.
[1] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.
[2] 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.
[3] KANG Hai-yan, HUANG Yu-xuan, CHEN Chu-qiao. Enhancing privacy for geographic information based on video analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 19-29.
[4] LIANG Xiao-lin, GUO Min, LI Jing. Parametric estimations for renewal-geometric process [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 53-57.
[5] 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.
[6] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[7] CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33.
[8] 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.
[9] YANG Chun-hua, CAI Jian-sheng. Classification on f-coloring of graphs with some restrictions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 37-38.
[10] 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.
[11] HE Yu-ping, WANG Zhi-wen, CHEN Xiang-en. Vertex-distinguishing total coloring of mC8 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(10): 24-30.
[12] WANG Wen-shu, LI Wei-guo, QIN Shu-lan. Application of a new accelerating Bregman iterative algorithm in the sparse least squares problems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(6): 92-98.
[13] LI Shi-ling, CHEN Xiang-en, WANG Zhi-wen. Vertex-Distinguishing E-Total coloring of complete bipartite graph K3,n with n≥18 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 68-71.
[14] 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.
[15] 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.
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