2-distance injective coloring of graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

Abstract

For a given graph $G=(V(G),E(G))$, a $2$-distance coloring of $G$ is a proper vertex coloring of the graph $G$ such that any pair of vertices at a distance of at most $2$ receive different colors. A vertex coloring of a graph $G$ is called an injective coloring if any two vertices $u$ and $v$ with a common neighbor, receive different colors.

A $2$-distance injective coloring of a graph $G$ is a vertex coloring in which any two vertices that share a common neighbor are assigned different colors, and any two vertices that share a common $2$-distance neighbor are also assigned different colors.

For any vertex $u \in V(G)$, the $2$-distance neighbors of $u$ are denoted by $N^{2}_{G}(u) = \{v \in V(G) : d_G(u,v) = 2\}$, and the $2$-distance degree of $u$ is given by

$deg^{2}_{G}(u) = |N^{2}_{G}(u)|$. Furthermore, let $\Delta(G)$ and $\Delta^{(2)}(G)$ represent the maximum degree and maximum $2$-distance degree of $G$, respectively.

In this paper, we initiate the study of the $2$-distance injective coloring of a graph. We demonstrate that, for any graph $G$, $$\Delta^{(2)} + 1 \leq \chi_{2i}(G) \leq \Delta(\Delta-1)[1 + {(\Delta-1)^{2}}] + 1$$ with sharp bounds, where $\chi_{2i}(G)$ represents the $2$-distance injective chromatic number of $G$. In particular, the trees $T$ and the grid graphs $P_n \square P_m$ achieve the lower bound.

Additionally, we explore the relationship between $2$-distance injective coloring and $2$-distance coloring of a graph, and determine $\chi_{2i}(G)$ for several well-known graphs $G$.

Keywords

Main Subjects

References

[1] A.A. Bertossi and M.A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio network, IEEE/ACM Trans. Networking 3 (1995), 441–449. https://doi.org/10.1109/INFCOM.1992.263490
[2] B. Brešar, B. Samadi, and I.G. Yero, Injective coloring of graphs revisited, Discrete Math. 346 (2023), no. 5, 113348.
https://doi.org/10.1016/j.disc.2023.113348
[3] Y. Bu, D. Chen, A. Raspaud, and W. Wang, Injective coloring of planar graphs, Discrete Appl. Math. 157 (2009), no. 4, 663–672. https://doi.org/10.1016/j.dam.2008.08.016
[4] G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman and Hall/CRC Taylor and Francis Group, LLC, 2009.
[5] D.W. Cranston, S.J. Kim, and G. Yu, Injective colorings of sparse graphs, Discrete Math. 310 (2010), no. 21, 2965–2973.
https://doi.org/10.1016/j.disc.2010.07.003
[6] G. Hahn, J. Kratochvíl, J. Širáň, and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002), no. 1-2, 179–192. https://doi.org/10.1016/S0012-365X(01)00466-6
[7] M.M. Halld´orsson, F. Kuhn, and Y. Maus, Distance-2 coloring in the CONGEST model, Proceedings of the 39th Symposium on Principles of Distributed Computing, 2020, pp. 233–242. https://doi.org/10.1145/3382734.3405706
[8] F. Kramer and H. Kramer, Un probleme de coloration des sommets d’un graphe, Comptes Rendus-Acad´emie des sciences 268 (1969), no. 7, 46–48.
[9] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008), no. 2-3, 422–426. https://doi.org/10.1016/j.disc.2006.11.059
[10] B. Lužar and R. Škrekovski, Counterexamples to a conjecture on injective colorings, Ars Math. Contemp. 8 (2015), no. 2, 291–295. https://doi.org/10.26493/1855-3974.516.ada
[11] B. Lužar, R. Škrekovski, and M. Tancer, Injective colorings of planar graphs with few colors, Discrete Math. 309 (2009), no. 18, 5636–5649. https://doi.org/10.1016/j.disc.2008.04.005
[12] S.S. Mirdamad and D.A. Mojdeh, $e$-injective coloring: 2-distance and injective coloring conjectures, J. Combin. Math. Combin. Comput. 123 (2024), 383–396.
[13] D.A. Mojdeh and B. Samadi, Further results on 2-distance coloring of graphs, J. Comb. Optim. 45 (2023), no. 7, 1–12.
https://doi.org/10.1007/s10878-022-00942-2
[14] B.S. Panda, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Discrete Appl. Math. 291 (2021), 68–87. https://doi.org/10.1016/j.dam.2020.12.006
[15] J. Song and J. Yue, Injective coloring of some graph operations, Appl. Math. Comput. 264 (2015), 279–283.
https://doi.org/10.1016/j.amc.2015.03.124
[16] G. Wegner, Graphs with given diameter and a coloring problem, Technical report, University of Dortmund, 1977.
[17] D.B. West, Introduction to Graph Theory, second ed., Prentice Hall, 2001.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 29 July 2026

Files

Share

How to cite

Statistics