中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 2: 111 - 127

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.02.010

Strong edge-coloring of planar graphs

Expand
  • 1. College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
    2. College of Xingzhi, Zhejiang Normal University, Lanxi 321100, Zhejiang, China

Received date: 2019-03-05

  Online published: 2022-05-27

Fold

Abstract

A strong edge coloring of graph $G$ is on the basis of the proper edge coloring and requiring any two edges at distance at most 2 receive distinct colors, the smallest integer of strong edge coloring called a figure of colors used strong edge chromatic number of $G$. In this paper, the configuration of the minimal counter example is given, and then the power transfer method is used to prove that the strong chromatic index of plane graphs with $g(G)\geq5$, $\Delta(G)\geq6$ and $5$-cycle do not intersect is at most $4\Delta(G)-1$.

Key words： planar graph; strong edge-coloring; girth; cycle

Cite this article

Yuehua BU, Heng ZHANG . Strong edge-coloring of planar graphs[J]. Operations Research Transactions, 2022 , 26(2) : 111 -127 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.010

References

1 Er?s P. Problems and results in combinatorial analysis and graph theory[C]// Proceedings of the First Japan Conference on Graph Theory and Applications, 1988: 81-92.
2 Andersen I D . The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108, 231- 252.
3 Hor$\acute{a}$k P , Qing H , Trotter W T . Induced matchings in cubic graphs[J]. Journal of 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 Huang M , Santana M , Yu G . Strong chromatic index of graphs with maximum degree four[J]. Electronic Journal of Combinatorics, 2018, 25 (3): #P3.31.
6 Molloy M , Reed B . A bound on the strong chromatic index of a graph[J]. Journal of Combinatorial Theory B, 1997, 69 (2): 103- 109.
7 Bruhn B , Joos F . A stronger bound for the strong chromatic index[J]. Combinatorics Probability & Computing, 2018, 27, 21- 43.
8 Bonamy M , Perrett T , Postle L . Colouring graphs with sparse neighbourhoods: bounds and Applications[J]. Journal of Combinatorial Theory, Series B, 2022, 155, 278- 317.
9 Faudree R J , Gya$\acute{a}$rfas A , Schelp R H , Tuza Zs . The strong chromatic index of graphs[J]. Ars Combinatoria, 1990, 29B, 205- 211.
10 Hud$\acute{a}$k D , Lu$\check{z}$ar B , Sot$\acute{a}$k R , et al. Strong edge-coloring of planar graph[J]. Discrete Mathematics, 2014, 324, 41- 49.
11 Bensmail J , Harutyunyan A , Hocquard H , et al. Strong edge-coloring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179, 229- 234.
Options
Outlines

/

〈 〉