آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 125 |
| تعداد مقالات | 1,580 |
| تعداد مشاهده مقاله | 1,733,025 |
| تعداد دریافت فایل اصل مقاله | 1,611,574 |
2-distance injective coloring of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 07 مرداد 1405 اصل مقاله (511.32 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30173.2346 | ||
| نویسندگان | ||
| Shahrzad Sadat Mirdamad؛ Doost Ali Mojdeh* | ||
| Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran | ||
| چکیده | ||
| 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$. | ||
| کلیدواژهها | ||
| Graph coloring؛ $2$-distance coloring؛ injective coloring؛ $2$-distance injective coloring | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 10 تعداد دریافت فایل اصل مقاله: 6 |
||