没有短圈的平面图的强边染色

Strong Edge Coloring of Planar Graphs without Short Cycles

图G的强边染色是在正常边染色的基础上,要求长为3的路上的任意两条边染不同的颜色,强边染色所用颜色的最小整数称为图G的强边色数.众所周知,平面图的强边色数至多是4Δ+4.文章首先给出极小反例的构型,然后通过权转移法,证明了没有3-,5-,6-,7-,8-圈及相交4-圈的平面图的强边色数至多是3Δ+1.

A strong edge coloring of a graph G is a proper edge coloring such that any two edges on a path of length three receive distinct colors. It is known that every planar graph has a strong edgecoloring with at most 4△＋4 colors. The configuration of a counterexample is given firstly, then through discharging roles, the strong chromatic index of a planar graph is proved to be at most 3△＋ 1 if G has no 3-, 5-, 6-, 7-,8-cycles and no intersecting 4-cycles.