不含短圈平面图的强边染色

Strong Edge Coloring of Planar Graphs without Short Cycles

摘要: 图G的强边染色是在正常边染色的基础上，要求距离不超过2的任意两条边染不同的颜色。强边染色所用颜色的最小整数称为图G的强边色数。文章首先给出极小反例的构型，然后通过权转移方法，证明了3-圈、4-圈互不相交且没有k-圈(5≤Κ≤10)的平面图的强边色数至多是3Δ(G)+1 。

Abstract: 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 edge chromatic number of the plane graph is at most 3Δ(G)+1  if G has no k-cycle (5≤Κ≤10) and the 3-cycle and 4-cycle are non-intersect each other.