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

作者：卜月华; 陈雯雯; 朱俊蕾

来源：运筹学学报, 2022, 1-10.

• injective-边染色
• 平面图
• 最大度
• 圈

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。

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