English

运筹学学报 >

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

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

 

平面图的强边染色

展开
  • 1. 浙江师范大学数学与计算机科学学院, 浙江金华 321004
    2. 浙江师范大学行知学院, 浙江兰溪 321100
卜月华  E-mail: yhbu@zjnu.edu.cn

收稿日期: 2019-03-05

  网络出版日期: 2022-05-27

基金资助

国家自然科学基金(11771403)

收起

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

摘要

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。

关键词： 平面图; 强边染色; 围长; 圈

本文引用格式

卜月华, 张恒 . 平面图的强边染色[J]. 运筹学学报, 2022 , 26(2) : 111 -127 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.010

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

参考文献

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
文章导航

/

〈 〉