Three edges $ e_1 $, $ e_2 $ and $ e_3 $ in a graph $ G $ are $ consecutive $ if they form a cycle of length $ 3 $ or a path in this order. A $ k $-$ injective\; edge\; coloring $ of a graph $ G $ is an edge coloring of $ G $, (not necessarily proper), such that if edges $ e_1 $, $ e_2 $, $ e_3 $ are consecutive, then $ e_1 $ and $ e_3 $ receive distinct colors. The minimum $ k $ for which $ G $ has a $ k $-injective edge coloring is called the $ injective\; edge\; coloring\; number $, denoted by $ \chi_i^{\prime}(G) $. In this paper, we consider the injective edge coloring numbers of generalized Petersen graphs $ P(n, 1) $ and $ P(n, 2) $. We determine the exact values of injective edge coloring numbers for $ P(n, 1) $ with $ n\geq 3 $, and for $ P(n, 2) $ with $ 4\leq n\leq 7 $. For $ n\geq 8 $, we show that $ 4\leq \chi_{i}^{'}(P(n, 2))\leq 5. $
Citation: Yanyi Li, Lily Chen. Injective edge coloring of generalized Petersen graphs[J]. AIMS Mathematics, 2021, 6(8): 7929-7943. doi: 10.3934/math.2021460
Three edges $ e_1 $, $ e_2 $ and $ e_3 $ in a graph $ G $ are $ consecutive $ if they form a cycle of length $ 3 $ or a path in this order. A $ k $-$ injective\; edge\; coloring $ of a graph $ G $ is an edge coloring of $ G $, (not necessarily proper), such that if edges $ e_1 $, $ e_2 $, $ e_3 $ are consecutive, then $ e_1 $ and $ e_3 $ receive distinct colors. The minimum $ k $ for which $ G $ has a $ k $-injective edge coloring is called the $ injective\; edge\; coloring\; number $, denoted by $ \chi_i^{\prime}(G) $. In this paper, we consider the injective edge coloring numbers of generalized Petersen graphs $ P(n, 1) $ and $ P(n, 2) $. We determine the exact values of injective edge coloring numbers for $ P(n, 1) $ with $ n\geq 3 $, and for $ P(n, 2) $ with $ 4\leq n\leq 7 $. For $ n\geq 8 $, we show that $ 4\leq \chi_{i}^{'}(P(n, 2))\leq 5. $
| [1] |
M. Alaeiyan, H. Karami, Perfect 2-colorings of the generalized Petersen graph, Proc. Indian Acad. Sci. Math. Sci., 126 (2016), 289–294. doi: 10.1007/s12044-016-0285-4
|
| [2] |
A. A. Bertossi, M. A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE/ACM Trans. Networking, 3 (1995), 441–449. doi: 10.1109/90.413218
|
| [3] | Y. Bu, W. Chen, Injective-edge coloring of planar graphs with girth at least 6, Journal of Zhejiang Normal University, 43 (2020), 19–25 (In Chinese). |
| [4] | Y. Bu, C. Qi, J. Zhu, Injective edge coloring of planar graphs, Adv. Math., 6 (2020), 675–684(In Chinese). |
| [5] |
Y. Bu, C. Qi, Injective edge coloring of sparse graphs, Discrete Mathematics, Algorithms and Applications, 10 (2018), 1850022. doi: 10.1142/S1793830918500222
|
| [6] |
D. M. Cardoso, J. O. Cerdeira, J. P. Cruz, C. Dominic, Injective edge coloring of graphs, Filomat, 33 (2019), 6411–6423. doi: 10.2298/FIL1919411C
|
| [7] | B. Ferdjallah, S. Kerdjoudj, A. Raspaud, Injective edge-coloring of sparse graphs, arXiv: 1907.0983v2 [math.CO], 2019. |
| [8] |
G. Hahn, J. Kratochv$\acute{i}$l, J. Sir$\acute{a}$, D. Sotteau, On the injective chromatic number of graphs, Discrete Math., 256 (2002), 179–192. doi: 10.1016/S0012-365X(01)00466-6
|
| [9] |
A. Kostochka, A. Raspaud, J. Xu, Injective edge-coloring of graphs with given maximum degree, Eur. J. Combin., 96 (2021), 103355. doi: 10.1016/j.ejc.2021.103355
|
| [10] | Z. Yang, B. Wu, Strong edge chromatic index of the generalized Petersen graphs, Appl. Math. Comput., 321 (2018), 431–441. |
| [11] | J. Yue, S. Zhang, X. Zhang, Note on the perfect EIC-graphs, Appl. Math. Comput., 289 (2016), 481–485. |
| [12] |
E. Zhu, Z. Li, Z. Shao, J. Xu, C. Liu, Acyclic 3-coloring of generalized Petersen graphs, J. Comb. Optim., 31 (2016), 902–911. doi: 10.1007/s10878-014-9799-9
|
Figures(20)
Yanyi Li, Lily Chen. Injective edge coloring of generalized Petersen graphs[J]. AIMS Mathematics, 2021, 6(8): 7929-7943. doi: 10.3934/math.2021460
DownLoad: