INJECTIVE COLORING OF CENTRAL GRAPHS

Shahrzad Sadat Mirdamad; Doost Ali Mojdeh

INJECTIVE COLORING OF CENTRAL GRAPHS

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

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.

Details

Primary Language

English

Subjects

Combinatorics and Discrete Mathematics (Excl. Physical Combinatorics)

Journal Section

Research Article

Authors

Shahrzad Sadat Mirdamad This is me
0009-0006-2129-6658
Iran

Doost Ali Mojdeh ^*
0000-0001-9373-3390
Iran

Publication Date

March 17, 2026

Submission Date

January 31, 2025

Acceptance Date

May 26, 2025

Published in Issue

Year 2026 Volume: 16 Number: 3

IZ

https://izlik.org/JA66WS57EU

Cite

RIS / Bibtex

APA

Mirdamad, S. S., & Mojdeh, D. A. (2026). INJECTIVE COLORING OF CENTRAL GRAPHS. TWMS Journal of Applied and Engineering Mathematics, 16(3), 369-385. https://izlik.org/JA66WS57EU

AMA

1.Mirdamad SS, Mojdeh DA. INJECTIVE COLORING OF CENTRAL GRAPHS. JAEM. 2026;16(3):369-385. https://izlik.org/JA66WS57EU

Chicago

Mirdamad, Shahrzad Sadat, and Doost Ali Mojdeh. 2026. “INJECTIVE COLORING OF CENTRAL GRAPHS”. TWMS Journal of Applied and Engineering Mathematics 16 (3): 369-85. https://izlik.org/JA66WS57EU.

EndNote

Mirdamad SS, Mojdeh DA (March 1, 2026) INJECTIVE COLORING OF CENTRAL GRAPHS. TWMS Journal of Applied and Engineering Mathematics 16 3 369–385.

IEEE

[1]S. S. Mirdamad and D. A. Mojdeh, “INJECTIVE COLORING OF CENTRAL GRAPHS”, JAEM, vol. 16, no. 3, pp. 369–385, Mar. 2026, [Online]. Available: https://izlik.org/JA66WS57EU

ISNAD

Mirdamad, Shahrzad Sadat - Mojdeh, Doost Ali. “INJECTIVE COLORING OF CENTRAL GRAPHS”. TWMS Journal of Applied and Engineering Mathematics 16/3 (March 1, 2026): 369-385. https://izlik.org/JA66WS57EU.

JAMA

1.Mirdamad SS, Mojdeh DA. INJECTIVE COLORING OF CENTRAL GRAPHS. JAEM. 2026;16:369–385.

MLA

Mirdamad, Shahrzad Sadat, and Doost Ali Mojdeh. “INJECTIVE COLORING OF CENTRAL GRAPHS”. TWMS Journal of Applied and Engineering Mathematics, vol. 16, no. 3, Mar. 2026, pp. 369-85, https://izlik.org/JA66WS57EU.

Vancouver

1.Shahrzad Sadat Mirdamad, Doost Ali Mojdeh. INJECTIVE COLORING OF CENTRAL GRAPHS. JAEM [Internet]. 2026 Mar. 1;16(3):369-85. Available from: https://izlik.org/JA66WS57EU