平面图的强边染色  

Strong edge-coloring of planar graphs

作　　者：卜月华 张恒[1] BU Yuehua;ZHANG Heng(College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,Zhejiang,China;College of Xingzhi,Zhejiang Normal University,Lanxi 321100,Zhejiang,China)

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江金华321004 [2]浙江师范大学行知学院,浙江兰溪321100

出　　处：《运筹学学报》2022年第2期111-127,共17页Operations Research Transactions

基　　金：国家自然科学基金(No.11771403)。

摘　　要：图G的强边染色是在正常边染色的基础上,要求距离不超过2的任意两条边染不同的颜色,强边染色所用颜色的最小整数称为图G的强边色数。本文首先给出极小反例的构型,然后通过权转移法,证明了g(G)≥5,Δ(G)≥6且5-圈不相交的平面图的强边色数至多是4Δ(G)-1。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 chromatic index of plane graphs with g(G)≥5,Δ(G)≥6 and 5-cycle do not intersect is at most 4Δ(G)-1.

关 键 词：平面图 强边染色 围长 圈 

分 类 号：O157.6[理学—数学]