平面图的强边染色

doi:10.15960/j.cnki.issn.1007-6093.2022.02.010

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 111-127.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.010

平面图的强边染色

卜月华¹^,²^,*(), 张恒¹

1. 浙江师范大学数学与计算机科学学院, 浙江金华 321004
2. 浙江师范大学行知学院, 浙江兰溪 321100

收稿日期:2019-03-05 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 卜月华 E-mail:yhbu@zjnu.edu.cn
作者简介:卜月华 E-mail: yhbu@zjnu.edu.cn
基金资助:
国家自然科学基金(11771403)

Strong edge-coloring of planar graphs

Yuehua BU¹^,²^,*(), Heng ZHANG¹

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:2019-03-05 Online:2022-06-15 Published:2022-05-27
Contact: Yuehua BU E-mail:yhbu@zjnu.edu.cn

摘要/Abstract

摘要：

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

关键词: 平面图, 强边染色, 围长, 圈

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

中图分类号:

O157.6

卜月华, 张恒. 平面图的强边染色[J]. 运筹学学报, 2022, 26(2): 111-127.

Yuehua BU, Heng ZHANG. Strong edge-coloring of planar graphs[J]. Operations Research Transactions, 2022, 26(2): 111-127.

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 11

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. doi: 10.1016/0012-365X(92)90678-9
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. doi: 10.1002/jgt.3190170204
4	Cranston D . Strong edge-coloring graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306, 2772- 2778. doi: 10.1016/j.disc.2006.03.053
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. doi: 10.1006/jctb.1997.1724
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. doi: 10.1016/j.jctb.2022.01.009
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. doi: 10.1016/j.disc.2014.02.002
11	Bensmail J , Harutyunyan A , Hocquard H , et al. Strong edge-coloring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179, 229- 234. doi: 10.1016/j.dam.2014.07.006

[1]	周成昊, 吕博轩, 周翰宇, 鲁海燕. 以商圈为中心的O2O动态外卖配送路径优化模型与算法[J]. 运筹学学报, 2022, 26(3): 17-30.
[2]	余桂东, 阮征, 舒阿秀. k圈图的最大Laplace分离度[J]. 运筹学学报, 2022, 26(2): 137-142.
[3]	李春梅, 王治文. Δ(G)=5的2-连通外平面图的邻点可区别全染色[J]. 运筹学学报, 2021, 25(4): 120-126.
[4]	刘瑶. 带松弛条件的图的强边着色[J]. 运筹学学报, 2021, 25(2): 115-126.
[5]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[6]	陈敏, 杨建民, 张豪, 王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136.
[7]	余桂东, 阮征, 舒阿秀, 于涛. 单圈图的次大(拉普拉斯)分离度[J]. 运筹学学报, 2020, 24(4): 128-134.
[8]	陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.
[9]	陈涛. 哈密尔顿平面图最小平衡二部划分的上界[J]. 运筹学学报, 2020, 24(3): 161-166.
[10]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[11]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[12]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[13]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[14]	陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.
[15]	丁超, 余桂东. 含偶圈图的Laplacian 谱刻画[J]. 运筹学学报, 2018, 22(4): 135-140.

平面图的强边染色

Strong edge-coloring of planar graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 11

相关文章 15

编辑推荐

Metrics

本文评价