摘要
图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.
出处
《南开大学学报（自然科学版）》
CAS
CSCD
北大核心
2015年第6期1-5,共5页
Acta Scientiarum Naturalium Universitatis Nankaiensis
基金
山西省青年科技研究基金(2013021001-1)
山西省高等学校科技研究开发项目(20121015)
关键词
平面图
强边染色
强边色数
planar graphs
strong edge coloring
strong chromatic index
