PACKING COLORINGS OF THE CORONA PRODUCT OF THE PATH $P_n$ AND THE CYCLE $C_n$ WITH AN EDGE $K_2$

Year 2026, Volume: 16 Issue: 1, 94 - 108, 08.01.2026

R. Sampathkumar R. Sampathkumar , T. Sivakaran R. Unnikrishnan

Abstract

Given a graph $G$ and a positive integer $i,$ an $i$-packing in $G$ is a subset $X$ of $V(G)$ such that the distance $d_G(u, v)$ between any two distinct vertices $u,v\,\in\,X$ is greater than $i.$ The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i,$ $i\in [k],$ where each $V_i$ is an $i$-packing. In this paper, we determine the packing chromatic number of the corona products of paths and cycles of small order (at most $11$ vertices) with an edge and obtain bounds for the packing chromatic number of corona products of paths and cycles of larger order with an edge.

Keywords

packing chromatic number , corona product of graphs , product of graphs

Thanks

The authors would like to thank the referee for suggestions which improved the presentation of the paper.

References

• Balakrishnan, R. and Ranganathan, K., (2012), A textbook of graph theory, Second Edition, Springer, New York.
• Bresar, B., Ferme, J., Klavzar, S. and Rall, D. F., (2020), A survey on packing colorings, Discussiones Mathematica Graph Theory, 40, pp. 923–970.
• Bresar, B., Klavzar, S. and Rall, D. F., (2007), On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math., 155, pp. 2303–2311.
• Dliou, K., (2025), Independence, matching and packing coloring of the iterated Mycielskian of graphs, Discrete Appl. Math., 361, pp. 22–33.
• Goddard W., Hedetniemi S. M., Hedetniemi S. T., Harris J. M. and Rall D. F., (2008), Broadcast chromatic numbers of graphs, Ars Combin., 86, pp. 33–49.
• Gregor, P., Kranjc, J., Luzar, B. and Storgel, K., (2024), Packing coloring of hypercubes with extended Hamming codes, Discrete Appl. Math., 359, pp. 269–277.
• Grochowski, H. and Junosza-Szaniawski, K., (2025), Partial packing coloring and quasi-packing coloring of the triangular grid, Discrete Math., 348, pp. 114308, 21.
• Laıche, D., Bouchemakh, I. and Sopena, E., (2017), Packing coloring of some undirected and oriented coronae graphs, Discussiones Mathematicae Graph Theory, 37, pp. 665–690.