平面图的强边染色

作者：卜月华^*; 张恒

来源：运筹学学报, 2022, 26(02): 111-127.

DOI：10.15960/j.cnki.issn.1007-6093.2022.02.010

• 平面图
• 强边染色
• 围长
• 圈

图G的强边染色是在正常边染色的基础上,要求距离不超过2的任意两条边染不同的颜色,强边染色所用颜色的最小整数称为图G的强边色数。本文首先给出极小反例的构型,然后通过权转移法,证明了g(G)≥5,Δ(G)≥6且5-圈不相交的平面图的强边色数至多是4Δ(G)-1。

• 单位
  浙江师范大学行知学院; 浙江师范大学