不含K_(1,3)^(+)图的强边染色

Strong edge-coloring of graphs without K_(1,3)^(+)

一个图G的强边染色是将颜色分配给所有的边,使得每个颜色类的导出子图是一个匹配。在图G的强边染色中所需的最小颜色数称为图G的强边色数,边e=uv的度记为d(e)=d(u)+d(v),图G的边度记为d(G)=min{d(e)|e∈E(G)}。证明最大度为Δ且图的边度大于顶点数的不含K_(1,3)^(+)图的强边色数至多是Δ^(2)-Δ+1。

The strong edge-coloring of a graph G is to assign colors to all edges,so that the derived subgraphs of each color class are a matching.The minimum number of colors required in the strong edge-coloring of a graph G is called the strong chromatic index of the graph G,the degree of edge e=uv is recorded as d(e)=d(u)+d(v),the edge degree of G is recorded as d(G)=min{d(e)|e∈E(G)}.This paper proves that the strong chromatic index of the graph without K_(1,3)^(+) with the maximum degreeΔand edge degree of the graph greater than the number of vertices is at mostΔ^(2)-Δ+1.