平面图的强边染色的一个结果

A Result on the Strong Edge Coloring of Planar Graphs

如果图G的一个正常边染色的任意有公共邻边的两条边的染色不相同,则它是图G的一个强边染色。图G的强边染色所需要的最小颜色数称作图G的强边色数。本文利用差值转移方法证明了最大顶点度为偶数且不小于6的平面图,如果其不含有3圈,则其强边色数不超过5△2/4,特别地,本文证明了最大顶点度为4的平面图,如果其围长不小于5,则其强边色数不超过20。

For a proper edge coloring of a simple graphG,if any two edges which are adjacent to a same edge have different colors,then,it is a strong edge coloring of G.The minimum number of colors of any strong edge colorings of G is the strong chromatic number of G.In this paper,by using discharging method,we proved that the strong chromatic number for planar graphs with even maximum degree which is at least 6 and without 3 cycles is no more than 5Δ~2/4,furthermore,we proved that 20 is an upper bound of the strong chromatic number of planar graphs with maximum degree 4 and girth at least 5.