稀疏图的列表单射边染色
List Injective Edge Coloring of Sparse Graphs
DOI: 10.12677/ORF.2022.123078, PDF,    科研立项经费支持
作者: 胡小兵, 黄宁戈, 陈莉莉*：华侨大学数学科学学院，福建 泉州
关键词: 稀疏图；单射边染色；权转移法；列表单射边染色；Sparse Graphs； Injective Edge Coloring； Discharging Method； List Injective Edge Coloring
摘要: 图G的单射边染色是对图G的边进行染色，使得如果三条边e1，e2，e3是连续的，那么e1和e3染不同的颜色。图G的单射边色数是所有单射边染色中所用颜色最少的颜色数。在本文中，我们考虑单射边染色的列表版本，得到在最大平均度条件限制下稀疏图的列表单射边色数的上界。
Abstract: An injective edge coloring of a graph G is a coloring of the edges of G, such that if three edges e1, e2, and e3 are consecutive, then e1 and e3 are colored differently. The injective edge coloring number is the smallest number of colors used in all injective edge colorings of G. In this paper, we consider the list injective edge coloring of graphs, and obtain some upper bounds of the list injective edge coloring number of sparse graphs in terms of the maximum average degree of G.
文章引用：胡小兵, 黄宁戈, 陈莉莉. 稀疏图的列表单射边染色[J]. 运筹与模糊学, 2022, 12(3): 738-747. https://doi.org/10.12677/ORF.2022.123078

参考文献

[1] Cardoso, D.M., Cerdeira, J.O., Dominic, C. and Cruz, J.P. (2019) Injective Edge Coloring of Graphs. Filomat, 33, 6411-6423. [Google Scholar] [CrossRef] 
[2] Hahn, G., Kratochvil, J., Siran, J. and Sotteau, D. (2002) On the Injective Chromatic Number of Graphs. Discrete Mathematics, 256, 179-192. [Google Scholar] [CrossRef] 
[3] Bertossi, A.A. and Bonuccelli, M.A. (1995) Code Assignment for Hidden Terminal Interference Avoidance in Multihop Packet Radio Networks. IEEE/ACM Transactions on Networking, 3, 441-449. [Google Scholar] [CrossRef] 
[4] Jin, J., Xu, B.G. and Zhang, X.Y. (2013) On the Complexity of Injective Colorings and its Generalizations. Theoretical Computer Science, 491, 119-126. [Google Scholar] [CrossRef] 
[5] Foucaud, F., Hocquard, H. and Lajou, D. (2021) Complexity and Algorithms for Injective Edge-Coloring in Graphs. Information Processing Letters, 170, Article No. 106121. [Google Scholar] [CrossRef] 
[6] 卜月华, 齐晨涛, 朱俊蕾. 平面图的单射边染色[J]. 数学进展, 2020, 49(6): 675-684.
[7] 卜月华, 陈雯雯. 围长至少是6的平面图的Injective-边染色[J]. 浙江师范大学学报, 2020, 43(1): 19-25.
[8] Li, Y.Y. and Chen, L. (2021) Injective Edge Coloring of Generalized Petersen Graphs. AIMS Mathematics, 6, 7929-7943. [Google Scholar] [CrossRef] 
[9] Yue, J., Zhang, S. and Zhang, X. (2016) Note on the Perfect EIC-Graphs. Applied Mathematics and Computation, 289, 481-485. [Google Scholar] [CrossRef] 
[10] Kostochka, A., Raspaud, A. and Xu, J.W. (2021) Injective Edge-Coloring of Graphs with Given Maximum Degree. European Journal of Combinatorics, 96, Article No. 103355. [Google Scholar] [CrossRef] 
[11] Bu, Y.H. and Qi, C.T. (2018) Injective Coloring of Sparse Graphs. Discrete Mathematics, Algorithms and Applications, 10, Article No. 1850022. [Google Scholar] [CrossRef] 
[12] Miao, Z.K., Song, Y.M. and Yu, G.X. (2022) Note on Injective Edge-Coloring of Graphs. Discrete Applied Mathematics, 310, 65-74. [Google Scholar] [CrossRef] 

为你推荐