不含短圈的平面图的injective边染色  

Injective edge coloring of planar graphs without short cycles

作　　者：卜月华 陈雯雯[1] 朱俊蕾 BU Yuehua;CHEN Wenwen;ZHU Junlei(Collegeof Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,Zhejiang,China;XingzhiCollege,ZhejiangNormalUniversity,Jinhua 321004,Zhejiang,China;College of Data Science,Jiaxing University,Jiaxing 314001,Zhejiang,China)

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江金华321004 [2]浙江师范大学行知学院,浙江金华321004 [3]嘉兴学院数据科学学院,浙江嘉兴314001

出　　处：《运筹学学报(中英文)》2024年第4期143-151,共9页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11771403,11901243);浙江省自然科学基金(No.LQ19A010005)。

摘　　要：2015年Cardoso等人在探究电台网络打包(PRN)问题时给出了injective-边染色的概念。图的k-injective-边染色是指对于图G给定一个边染色f:E(G)→C={1,2,…,k},若e_(1),e_(2),e_(3)是G中连续的3条边,则有f(e_(1))≠f(e_(3))。图G的injective-边染色数是指使得图G存在一个k-injective-边染色的最小整数k,用χi'(G)表示。本文运用极小反例和权转移方法证明了:对不包含k-圈且4--圈互不相交的平面图G,有χi'(G)≤3△(G)-2,其中5≤k≤10。To explore radio network packaging issues,Cardoso et al.proposed the concept of injective edge coloring of a graph in 2015.A k-injective edge coloring of G is a coloring of the edges of G,f:E(G)→C={1,2,…,k},such that if e_(1),e_(2),e_(3) are three consecutive edges in G,then f(e_(1))≠f(e_(3)),where e_(1),e_(2) and e_(3) are consecutive if they form a path or a cycle of length 3.The injective edge coloring number,denoted by χ_(i)^'(G),is the minimum number of colors such that G has such a coloring.In this paper,we use minimal counter example and power transfer method to prove that if G is a planar graph without k-cycles and 4^(-)-cycles disjoint,thenχ(i)^'(G)≤3△(G)-2,where 5≤k≤10.

关 键 词：injective-边染色 平面图 最大度 圈 

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