### 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

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!