平面图的强边染色

Strong edge-coloring of planar graphs

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

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)≥5,Δ(G)≥6 and 5-cycle do not intersect is at most 4Δ(G)-1.