ON SEMISTRONG EDGE-COLORINGS OF OUTERPLANAR GRAPHS

Aram K. Drambyan; Hamlet V. Mikaelyan

doi:10.46991/PYSUA.2025.59.2.032

Authors

Aram K. Drambyan Russian-Armenian University (RAU), Armenia https://orcid.org/0009-0002-2691-6976
Hamlet V. Mikaelyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia https://orcid.org/0009-0006-9642-7667

DOI:

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

Keywords:

edge-coloring, semistrong edge-coloring, semistrong chromatic index, outerplanar graphs

Abstract

A matching M of a graph G is called semistrong, if every edge of M has a vertex of degree one in the induced subgraph by the vertices of M. A semistrong edge-coloring of a graph G is a proper edge-coloring in which every color class induces a semistrong matching. The minimum number of colors required for a semistrong edge-coloring is called the semistrong chromatic index of G and denoted by $\chi'_{ss}(G)$. In this paper, we propose a new approach for constructing semistrong edge-colorings and provide an upper bound on the semistrong chromatic index of outerplanar graphs.

References

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

Chartrand G., Harary F. Planar Permutation Graphs. Annales de l'institut Henri Poincaré. Section B. Calcul des probabilités et statistiques 3 (1967), 433-438. http://www.numdam.org/item?id=AIHPB_1967__3_4_433_0

Fouquet J.L., Jolivet J.L. Strong Edge-Colorings of Graphs and Applications to Multi-k-Gons. Ars Combinatoria 16 (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

bibitem{horak}

Hor{'a}k P., Qing H., Trotter W.T. Induced Matchings in Cubic Graphs. textit{J. Graph Theory} {bf 17} (1993), 151--160.

href{ https://doi.org/10.1002/jgt.3190170204}{ https://doi.org/10.1002/jgt.3190170204}

Huang M., Santana M., Yu G. Strong Chromatic Index of Graphs with Maximum Degree Four. Electron. J. Combinator. 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. Combin., Probab. Comput. I 27 (2018), 21-43. https://doi.org/10.1016/j.endm.2015.06.038

Hurley Eoin, Rémi de Joannis de Verclos, Kang R.J. An Improved Procedure for Coloring Graphs of Bounded Local Density. 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

Gy'arf'as A., Hubenko A. Semistrong Edge Coloring of Graphs. J. Graph Theory 49 (2005), 39-47. https://doi.org/10.1002/jgt.20061

Lužar B., Mockovčiaková M., Soták R. Revisiting Semistrong Edge-Coloring of Graphs. J. Graph Theory 105 (2024), 612-632. https://doi.org/10.1002/jgt.23059

Hocquard H., Ochem P., Valicov P. Strong Edge-Coloring and Induced Matchings. Inform. Process. Lett. 113 (2013), 836-843. https://doi.org/10.1016/j.ipl.2013.07.026

Fleischner H.J., Geller D.P., Harary F. Outerplanar Graphs and Weak Duals. J. Indian Math. Soc. 38 (1974), 215-219. https://informaticsjournals.co.in/index.php/jims/article/view/16694

Whitney H. Congruent Graphs and the Connectivity of Graphs}. Hassler Whitney Collected Papers (1992), 61-79. https://doi.org/10.1007/978-1-4612-2972-8_4

Wang Y., Wang P., Wang W. Strong Chromatic Index of K_4-Minor Free Graphs. Inform. Process. Lett. 129 (2018), 53-56. https://doi.org/10.1016/j.ipl.2017.09.007