一些稀疏图的强边染色  

Strong Edge-coloring of Some Sparse Graphs

作　　者：秦利忠 吕剑波 李建喜 QIN Lizhong;Lü Jianbo;LI Jianxi(State Owned Assets Management Division,Yulin Normal University,Yulin,Guangxi,537000,P.R.China;School of Mathematics and Statistics,Guangxi Normal University,Guilin,Guangxi,541004,P.R.China;School of Mathematics and Statistics,Minnan Normal University,Zhangzhou,Fujian,363000,P.R.China)

机构地区：[1]玉林师范学院国有资产管理处,广西玉林537000 [2]广西师范大学数学与统计学院,广西桂林541004 [3]闽南师范大学数学与统计学院,福建漳州363000

出　　处：《数学进展》2022年第1期41-52,共12页Advances in Mathematics（China）

基　　金：supported by Project to Improve the Basic Research Ability of Young and Middle-aged Teachers in Guangxi Universities(No.2020KY14020);supported by NSFC(No.12161010);Youth Science Foundation of Guangxi(No.2019JJB110007);supported by NSF of Fujian(No.2021J02048)。

摘　　要：图G的强边染色是指对图G进行正常边染色使得任意长度为3的路的三条边染不同的颜色.图G的强边色数,记为χ’_(s)(G),是使得图G是强k边着色的最小正整数kk.2015年,Zang[arXiv:1510.00785]证明了:最大度△(G)=5的图G,χ’_(s)(G)≤37.本文证明了:最大度△(G)=5且最大平均度小于8/3(或者14/5)的图G,χ’_(s)(G)≤13(或者14).另外,本文证明了:最大度△(G)≥3的不含K_(2,3)-图子式的图G,χ’_(s)(G)≤4△(G)-6,这个界是紧的.A strong edge-coloring of a graph G is a proper edge-coloring such that every path of length 3 uses three different colors.The strong chromatic index of G,denoted by χ’_(s)(G),is the least possible number of colors in a strong edge-coloring of G.In 2015,Zang[arXiv:1510.00785]proved thatχ’_(s)(G)≤37 for any graph with maximum degreeΔ(G)=5.In this paper,we prove that if G is a graph withΔ(G)=5 and maximum average degree less than8/3(resp.,(14)/5),thenχ’_(s)(G)≤13(resp.,14).In addition,we show that if G is a K_(2,3)-minor free graph with maximum degreeΔ(G)≥3,thenχ’_(s)(G)≤4Δ(G)-6,and the bound is sharp.

关 键 词：强边染色 稀疏图 不含K -图子式的图 

分 类 号：O157.5[理学—数学]