JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2020, Vol. 55 ›› Issue (9): 36-41.doi: 10.6040/j.issn.1671-9352.0.2019.610

Previous Articles    

Adjacent vertex distinguishing edge coloring of planar graphs without intersecting triangles

LIU Zhuo-ya, XU Chang-qing*   

  1. School of Science, Hebei University of Technology, Tianjin 300401, China
  • Published:2020-09-17

PDF (PC)

282

Abstract: A k-adjacent vertex distinguishing edge coloring of a graph G is a proper k-edge coloring of G such that for any two adjacent vertices u and v, the color set of edges incident with u is different from the color set of edges incident with v. The least k for a k-adjacent vertex distinguishing edge coloring of G is the adjacent vertex distinguishing chromatic number, denoted by χ'a(G). By using the discharging method, we study the adjacent vertex distinguishing chromatic number of a planar graph without intersecting triangles, and get the conclusion: if G is a planar graph without intersecting triangles, then χ'a(G)≤max{Δ(G)+2,10}.

Key words: planar graph, adjacent vertex distinguishing edge coloring, adjacent vertex distinguishing chromatic number

CLC Number: 

  • O157.5
[1] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(5):623-626.
[2] HOR(ˇoverN)ÁK M, HUANG Danjun, WANG Weifan. On neighbor-distinguishing index of planar graphs[J]. Journal of Graph Theory, 2014, 76(4):262-278.
[3] ZHU Junlei, BU Yuehua, DAI Yun. Upper bounds for adjacent vertex-distinguishing edge coloring[J]. Journal of Combinatorial Optimization, 2018, 35:454-462.
[4] BONAMY M, BOUSQUET N, HOCQUARD H. Adjacent vertex-distinguishing edge coloring of graphs[C] // The Seventh European Conference on Combinatorics, Graph Theory and Applications, 2013, 16:313-318.
[5] WANG Weifan, HUANG Danjun. A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree[J]. SIAM Journal on Discrete Mathematics, 2015, 29(4):2412-2431.
[6] HUANG Danjun,MIAO Zhengke,WANG Weifan. Adjacent vertex distinguishing indices of planar graphs without 3-cycles[J]. Discrete Mathematics, 2015, 338(3):139-148.
[7] 严丞超,黄丹君,王维凡. 围长至少为 4 的可平面图的邻点可区别边染色[J]. 数学研究,2012,45(4):331-341. YAN Chengchao, HUANG Danjun, WANG Weifan. Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least four[J]. Journal of Mathematical Study, 2012, 45(4):331-341.
[1] CHEN Hong-yu, ZHONG Bin. Linear 2-arboricity of planar graphs without intersecting 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(7): 38-45.
[2] LIU Jia, SUN Lei. Planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 31-40.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] MENG Xian-yong, GUO Jian-hua, SU Ben-tang. The complete coloring of 3-regular Halin graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(12): 127-129.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] XUE Ling1, WU Jian-liang2*. Total chromatic number of planar graphs with few short cycles [J]. J4, 2012, 47(9): 84-87.
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