Abstract:

In this work, we study the injective chromatic number of the graph C^k_n, which is a graph obtained from C_n by adding an edge to any two distinct vertices with distance 2 to k on C_n. An injective coloring of a graph G is a vertex coloring in which any pair of vertices with a common neighbor are assigned different colors. The injective chromatic number \chi_i (G) of a graph G is the least positive integer k such that G has an injective k-coloring. In this work, we determine \chi_i (C^k_n) for all n and k. When n \leq 2k+1, the graph C_n^k becomes a complete graph K_n, with injective chromatic number n. For larger values of n, we obtain the following main results: if r=0, then \chi_i (C^k_n) = 2k+1, while if 1 \leq r \leq 2k, then \chi_i (C^k_n)=2k+\tilde{x}+1, where \tilde{x} is the largest natural number such that 1+(2k+1)\lceil \frac{n}{2k+x}\rceil > n. Additionally, we find \chi_i (P^k_n) for all n and k where P^k_n is a graph obtained similarly from a path P_n.