特殊平面图的强边染色

摘要

A strong edge coloring of a graph G is a proper edge coloring such that every path of length 3 uses three colors.It is known that every planar graph with maximum degree Δ has a strong edge-coloring with at most 4Δ + 4 colors.In this paper,we show that 3Δ + 1 colors suffice if the planar graph has no cycles of length among [3,4,6] and no intersecting 5-cycles.%强边染色是在正常边染色的基础上,要求长为3的路用3种不同的颜色染色.众所周知,最大度是△的平面图至多用4△+4种颜色进行强边染色.文章证明了没有3,4,6-圈且5-圈不相交的平面图至多可用3△+1种颜色进行强边染色.