Injective edge coloring of generalized Petersen graphs

Abstract

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. $

Keywords

• $ k $-injective edge coloring
• injective edge coloring number
• generalized petersen graph