一些稀疏图的强边染色

Strong Edge-coloring of Some Sparse Graphs

图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.