INJECTIVE COLORING OF CENTRAL GRAPHS

Year 2026, Volume: 16 Issue: 3, 369 - 385, 17.03.2026

Shahrzad Sadat Mirdamad Doost Ali Mojdeh

https://izlik.org/JA66WS57EU

Abstract

For a given graph $G=(V(G),E(G))$, researchers have introduced different colorings based on the distances of the vertices. An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that no two vertices with a common neighbor receive the same color. The injective chromatic number of $G$, denoted by $\chi_{i}(G)$, is the minimum number of colors required for an injective coloring of $G$. The concept of a central graph of any graph has been a widely studied topic among mathematical researchers and graph theorists nowadays.
The central graph of a given graph $G$, denoted by $C(G)$, is the graph obtained by subdividing each edge of $G$ exactly once and also adding an edge between each pair of non-adjacent vertices of $G$.

In this work, we present some results on injective coloring of central graph $C(G)$ of $G$. We show that for a graph $G$ of order $n$ and maximum degree $\Delta(G)$,
$$n-1\le \chi_{i}(C(G))\leq n^{2}-3n-(n-3)\Delta(G)+3.$$

Next, we will closely examine the injective chromatic number of the central graph of some special graphs and trees.
Finally, for any graph $H$, and the corona product ($H\circ K_1$), ($H\circ K_2$),
we will have a precise determination of the injective chromatic number of $C(H\circ K_1)$ and $C(H\circ K_2)$ in terms of
$\chi_{i}(C(H))$ and order of $H$.

Keywords

Graph coloring , injective coloring , central graphs , corona product

References

• Bertossi, A. A. and Bonuccelli, M. A., (1995), Code assignment for hidden terminal interference avoidance in multihop packet radio network, IEEE/ACM Trans. Networking., 3, pp. 441-449.
• Bu, Y., Chen, D., Raspaud, A. and Wang, W., (2009), Injective coloring of planar graphs, Discrete Applied Mathematics., 157(4), pp. 663-672.
• Chartrand, G. and Zhang, P., (2009), Chromatic Graph Theory, Chapman and Hall/CRC Taylor and Francis Group, LLC.
• Cranston, D. W., Kim, S. J. and Yu, G., (2010), Injective colorings of sparse graphs, Discrete Mathematics., 310(21), pp. 2965-2973.
• Frucht, R. and Harary, F., (1970), On the corona of two graphs, Aequationes Mathematicae., 4(3), pp. 322-325.
• Hahn, G., Kratochvil, J., Siran, J. and Sotteau, D., (2002), On the injective chromatic number of graphs, Discrete Mathematics., 256(1-2), pp. 179-192.
• Luzar, B., Skrekovski, R. and Tancer, M., (2009), Injective colorings of planar graphs with few colors, Discrete Mathematics., 309(18), pp. 5636-5649.
• Mirdamad, Sh. S. and Mojdeh, D. A., (2024), e-injective coloring: 2-distance and injective coloring conjectures, Jornal Combinatorial Mathematics and Combinatorial, Computing, 123, pp. 383-396.
• Panda, B. S., (2021), Injective coloring of some subclasses of bipartite graphs and chordal graphs, Discrete Applied Mathematics., 291, pp. 68-87.
• Song, J. and Yue, J., (2015), Injective coloring of some graph operations, Applied Mathematics and Computation., 264, pp. 279-283.
• Vernold, J., (2007), Harmonious coloring of total graphs, n-leaf, central graphs, circumdetic graphs. Ph.D Thesis Bharathia University Coimbatore India.
• West, D.B., (2001), Introduction to Graph Theory (Second Edition), Prentice Hall, USA.