JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (08): 10-13.doi: 10.6040/j.issn.1671-9352.0.2015.165

Previous Articles     Next Articles

Strong edge coloring of a class of planar graphs

MENG Xian-qing1,2   

  1. 1. School of Mathematics and Computer Sciences, Shanxi Datong University, Datong 037009, Shanxi, China;
    2. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2015-04-17 Online:2015-08-20 Published:2015-07-31

PDF (PC)

605

Abstract: A strong edge coloring of a graph G is an assignment of colors to the edges of the graph such that any two edges at distance at most 2 receive distinct colors. It is known that every planar graph has a strong edge-coloring with at most 4Δ+4 colors. It is proved that planar graph G has a strong edge-coloring with at most 3Δ+1 colors if G has no k-cycles with 4≤k≤10 and no intersecting 3-cycles (that is, every vertex is incident with at most one cycle of length 3).

Key words: planar, cycle, srtong chromaic index, strong edge coloring

CLC Number: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan, 1976.
[2] ANDERSEN L D. The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108:231-252.
[3] HORÁK P, HE Qing, TROTTER W T. Induced matchings in cubic graphs[J]. Graph Theory, 1993, 17(2):151-160.
[4] CRANSTON D. Strong edge-coloring graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306:2772-2778.
[5] FAUDREE R J, GYSRFAS A, SCHELP R H, et al. The strong chromatic index of graphs[J]. Ars Combin, 1990, 29B:205-211.
[6] BORODIN O V, IVANOVA A O. Precise upper bound for the strong edge chromatic number of sparse planar graphs[J]. Discuss Math Graph Theory, 2013, 33:759-770.
[7] MONTASSIER M, PÊCHER A, RASPAUD A. Strong chromatic index of planar graphs with large girth[J]. Graph Theory and Applications, CRM Series, 2013, 16:265-270.
[8] HUDÁK D, LU?AR B, SOTÁK R, et al. Strong edge-coloring of planar graphs[J]. Discrete Mathematics, 2014, 324:41-49.
[9] BENSMAIL J, HARUTYUNYAN A, HOCQUARD H, et al. Strong edge-coloring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179:229-234.
[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] 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.
[6] YU Xiao-lan. Global dimensions of cocycle deformations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 39-43.
[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] BAI Dan, ZUO Lian-cui. The(d,1)-total labelling of the cube of cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 59-64.
[9] WANG Jia-jiang, CHEN Ling, MEN Yu-tao, JI Chen. The feasibility study on shorten treatment cycle of dental implantation and split-root technique joint repair [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(3): 40-43.
[10] 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.
[11] WU Zi-juan, CHEN Yuan-yuan, ZHANG Liang-yun. Quasidimodule algebras over Hopf quasigroups and Yetter-Drinfeld quasimodule algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(10): 28-33.
[12] 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.
[13] XUE Li-xia, LI Zhi-hui, XIE Jia-li. A note on the optimal information rate of hypercycle access structure with three hyperedges [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(11): 60-66.
[14] WANG Shan-shan, QI En-feng. On the number of contractible edges of longest cycles in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(10): 27-31.
[15] ZHANG Shao-hua, YAN Jin, LI Shuo. Disjoint 4-cycles and 8-cycles in graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 1-4.
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