ON STRONG CHROMATIC INDEX OF SOME OPERATIONS ON GRAPHS

Aram K.  Drambyan

doi:10.46991/PYSUA.2025.59.1.001

Authors

Aram K. Drambyan Russian-Armenian University (RAU), Armenia

DOI:

https://doi.org/10.46991/PYSUA.2025.59.1.001

Keywords:

edge-coloring, strong edge-coloring, strong chromatic index, corona product, Mycielskian

Abstract

A strong edge-coloring of a graph $G$ is a mapping $\phi : E(G) \rightarrow \mathbb{N}$ such that the edges at distance $0$ or $1$ receive distinct colors. The minimum number of colors required for such a coloring is called the strong chromatic index of $G$ and is denoted by $\chi_s'(G)$. In this paper, we investigate the strong chromatic index of the Mycielskian $\mu(G)$ of graphs $G$ and corona products $G \odot H$ of graphs $G$ and $H$. In particular, we give tight lower and upper bounds on $\chi_s'(G \odot H)$. Moreover, we provide specific structural criteria, under which the upper bound is sharp. We also derive tight lower and upper bounds on $\chi_s'(\mu(G))$ for Mycielskian of graphs.

References

West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey (2001). https://dwest.web.illinois.edu/igt/

Fouquet J.L., Jolivet J.L. Strong Edge-colorings of Graphs and Applications to Multi-k-Gons. Ars Combinatoria 16(A) (1983), 141-150.

Andersen L.D. The Strong Chromatic Index of a Cubic Graph is at Most 10. Discrete Math. 108 (1992), 231-252. https://doi.org/10.1016/0012-365X(92)90678-9

Hor'ak P., Qing H., Trotter W.T. Induced Matchings in Cubic Graphs. J. Graph Theory 17 (1993), 151-160. https://doi.org/10.1002/jgt.3190170204

Cranston D.W. Strong Edge-coloring of Graphs with Maximum Degree 4 Using 22 Colors. Discrete Math. 306 (2006), 2772-2778. https://doi.org/10.1016/j.disc.2006.03.053

Huang M., Santana M., Yu G. Strong Chromatic Index of Graphs with Maximum Degree Four. Electron. J. Comb. 25 (2018), 3-31. https://doi.org/10.37236/7016

Chung F.R.K., Gy'arf'as A., Trotter W.T., Tuza Z. The Maximum Number of Edges in 2K_2-free Graphs of Bounded Degree. Discrete Math. 81 (1990), 129-135. https://doi.org/10.1016/0012-365X(90)90144-7

Bruhn H., Joos F. A Stronger Bound for the Strong Chromatic Index. Electron. Notes Discrete Math. 49 (2015), 277-284. https://doi.org/10.1016/j.endm.2015.06.038

Eoin H., Rémi de Joannis de Verclos, Kang R.J. An Improved Procedure for Colouring Graphs of Bounded Local Density. In: Proc. of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics (2020), 135-148. https://doi.org/10.19086/aic.2022.7

Frucht R.W., Harary F. On the Corona of Two Graphs. Aequ. Math. 4 (1970), 322-325. https://doi.org/10.1007/BF01844162

Rohan Sh., Adhikari B., Mishra A. Structural and Spectral Properties of Coronagraphs. Discrete Appl. Math. 228 (2017), 14-31. https://doi.org/10.1016/j.dam.2017.01.005

Arumugam S., Lee Y.C., Premalatha K., Wang T.M. On Local Antimagic Vertex Coloring for Corona Products of Graphs. arXiv preprint:1808.04956 (2018). https://doi.org/10.48550/arXiv.1808.04956

Mycielski J. Sur Le Coloriage Des Graphs. In: Colloquium Mathematicae 3 (1955), 161-162. http://eudml.org/doc/210000

Rudnicki P., Stewart L. The Mycielskian of a Graph. Formalized Mathematics 19 (2011), 27-34. http://eudml.org/doc/267007

Miškuf J., Škrekovski R., Tancer M. Backbone Colorings and Generalized Mycielski Graphs. SIAM J. Discrete Math. 23 (2009), 1063-1070. https://doi.org/10.1137/080717596

Togni O. Strong Chromatic Index of Products of Graphs. Discrete Math. and Theoretical Comp. Sci. 9 (2007), 47-56. https://doi.org/10.46298/dmtcs.414

Thiru V.S., Balaji S. Strong Chromatic Indices of Certain Binary Operations on Graphs. Discrete Math., Algorithms Appl. 16 (2024), 2350073. https://doi.org/10.1142/S1793830923500738