{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T05:05:16Z","timestamp":1764133516034,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T00:00:00Z","timestamp":1643760000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T00:00:00Z","timestamp":1643760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Sz\u00e9chenyi 2020 programme","award":["EFOP-3.6.1-16-2016-00015"],"award-info":[{"award-number":["EFOP-3.6.1-16-2016-00015"]}]},{"name":"National Research, Development and Innovation Office","award":["SNN 129364"],"award-info":[{"award-number":["SNN 129364"]}]},{"name":"ELKH Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A strong edge coloring of a graph <jats:italic>G<\/jats:italic> is a proper edge coloring of <jats:italic>G<\/jats:italic> such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product structure from which the unitary Cayley graphs emerge. We then go on to give tight bounds for the strong chromatic index of the Cartesian product of two trees, including an exact formula for the product in the case of stars. Further, we give bounds for the strong chromatic index of the product of a tree with a cycle. For any tree, those bounds may differ from the actual value only by not more than a small additive constant (at most 2 for even cycles and at most 4 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by 4.<\/jats:p>","DOI":"10.1007\/s00373-021-02408-4","type":"journal-article","created":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T08:03:33Z","timestamp":1643789013000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Strong Edge Coloring of Cayley Graphs and Some Product Graphs"],"prefix":"10.1007","volume":"38","author":[{"given":"Suresh","family":"Dara","sequence":"first","affiliation":[]},{"given":"Suchismita","family":"Mishra","sequence":"additional","affiliation":[]},{"given":"Narayanan","family":"Narayanan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3235-9221","authenticated-orcid":false,"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,2]]},"reference":[{"key":"2408_CR1","doi-asserted-by":"publisher","first-page":"#R117","DOI":"10.37236\/206","volume":"16","author":"R Akhtar","year":"2009","unstructured":"Akhtar, R., Boggess, M., Jackson-Henderson, T., Karpman, R., Jim\u00e9nez, I., Kinzel, A., Pritikin, D.: On the unitary Cayley graph of a finite ring. Electron. J. Combin. 16, #R117 (2009)","journal-title":"Electron. J. Combin."},{"issue":"1","key":"2408_CR2","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0097-3165(85)90048-2","volume":"40","author":"Noga Alon","year":"1985","unstructured":"Alon, Noga: An extremal problem for sets with applications to graph theory. J. Combin. Theory Ser A 40(1), 82\u201389 (1985)","journal-title":"J. Combin. Theory Ser A"},{"issue":"1\u20133","key":"2408_CR3","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(92)90678-9","volume":"108","author":"Lars D\u00f8vling Andersen","year":"1992","unstructured":"Andersen, Lars D\u00f8vling: The strong chromatic index of a cubic graph is at most 10. Discret. Math. 108(1\u20133), 231\u2013252 (1992)","journal-title":"Discret. Math."},{"key":"2408_CR4","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/j.endm.2015.06.104","volume":"49","author":"Julien Bensmail","year":"2015","unstructured":"Bensmail, Julien, Bonamy, Marthe, Hocquard, Herv\u00e9: Strong edge coloring sparse graphs. Electron. Notes Discret. Math. 49, 773\u2013778 (2015)","journal-title":"Electron. Notes Discret. Math."},{"key":"2408_CR5","first-page":"1","volume-title":"Surveys in Combinatorics, volume 82 of London Mathematical Society Lecture Notes","author":"JC Bermond","year":"1983","unstructured":"Bermond, J.C., Bond, J., Paoli, M., Peyrat, C.: Graphs and interconnection networks: diameter and vulnerability. In: Lloyd, E.K. (ed.) Surveys in Combinatorics, volume 82 of London Mathematical Society Lecture Notes, pp. 1\u201330. Cambridge University Press (1983)"},{"key":"2408_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2003.11.013","volume":"282","author":"P Berrizbeitia","year":"2004","unstructured":"Berrizbeitia, P., Giudici, R.E.: On cycles in the sequence of unitary cayley graphs. Discret. Math. 282, 1\u20133 (2004)","journal-title":"Discret. Math."},{"issue":"1","key":"2408_CR7","first-page":"35","volume":"62","author":"Valentin Borozan","year":"2015","unstructured":"Borozan, Valentin, Montero, Leandro, Narayanan, Narayanan: Further results on strong edge-colourings in outerplanar graphs. Australas. J. Combin. 62(1), 35\u201344 (2015)","journal-title":"Australas. J. Combin."},{"issue":"1\u20133","key":"2408_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0012-365X(93)90286-3","volume":"122","author":"RA Brualdi","year":"1993","unstructured":"Brualdi, R.A., Massey, J.J.Q.: Incidence and strong edge colorings of graphs. Discret. Math. 122(1\u20133), 51\u201358 (1993)","journal-title":"Discret. Math."},{"key":"2408_CR9","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.endm.2015.06.038","volume":"49","author":"Henning Bruhn","year":"2015","unstructured":"Bruhn, H., Joos, F.: A stronger bound for the strong chromatic index. Electron. Notes Discret. Math. 49, 277\u2013284 (2015)","journal-title":"Electron. Notes Discret. Math."},{"key":"2408_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-642-54423-1_36","volume-title":"LATIN 2014: Theoretical Informatics","author":"P Chalermsook","year":"2014","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Coloring graph powers: Graph product bounds and hardness of approximation. In: Alberto, P., Alfredo, V. (eds.) LATIN 2014: Theoretical Informatics. Lecture Notes in Computer Science, vol. 8392, pp. 409\u2013420. Springer, Berlin, Heidelberg (2014)"},{"issue":"12","key":"2408_CR11","doi-asserted-by":"publisher","first-page":"2348","DOI":"10.1016\/j.disc.2015.04.031","volume":"338","author":"GJ Chang","year":"2015","unstructured":"Chang, G.J., Chen, S.-H., Hsu, C.-Y., Hung, C.-M., Lai, H.-L.: Strong edge-coloring for jellyfish graphs. Discret. Math. 338(12), 2348\u20132355 (2015)","journal-title":"Discret. Math."},{"key":"2408_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0012-365X(90)90144-7","volume":"81","author":"FRK Chung","year":"1990","unstructured":"Chung, F.R.K., Gy\u00e1rf\u00e1s, A., Trotter, W.T., Tuza, Zs.: The maximum number of edges in $$2{K}_2$$-free graphs of bounded degree. Discret. Math. 81, 129\u2013135 (1990)","journal-title":"Discret. Math."},{"issue":"21","key":"2408_CR13","doi-asserted-by":"publisher","first-page":"2772","DOI":"10.1016\/j.disc.2006.03.053","volume":"306","author":"Daniel W Cranston","year":"2006","unstructured":"Cranston, D.W.: Strong edge-coloring of graphs with maximum degree 4 using 22 colors. Discret. Math. 306(21), 2772\u20132778 (2006)","journal-title":"Discret. Math."},{"key":"2408_CR14","first-page":"121","volume":"18","author":"J Dejter","year":"1995","unstructured":"Dejter, J., Giudici, R.E.: On unitary Cayley graphs. J. Combin. Math. Combin. Comput. 18, 121\u2013124 (1995)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"2408_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0012-365X(88)90196-3","volume":"72","author":"Paul Erd\u0151s","year":"1988","unstructured":"Erd\u0151s, P.: Problems and results in combinatorial analysis and graph theory. Discret. Math. 72, 81\u201392 (1988)","journal-title":"Discret. Math."},{"issue":"1\u20132","key":"2408_CR16","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0012-365X(89)90163-5","volume":"78","author":"RJ Faudree","year":"1989","unstructured":"Faudree, R.J., Gy\u00e1rf\u00e1s, A., Schelp, R.H., Tuza, Z.: Induced matchings in bipartite graphs. Discret. Math. 78(1\u20132), 83\u201387 (1989)","journal-title":"Discret. Math."},{"unstructured":"Faudree, R.J., Gy\u00e1rf\u00e1s, A., Schelp, R.H., Tuza, Zs.: The strong chromatic index of graphs. Ars Combin. 29B, 205\u2013211 (1990)","key":"2408_CR17"},{"key":"2408_CR18","first-page":"141","volume":"16A","author":"JL Fouquet","year":"1983","unstructured":"Fouquet, J.L., Jolivet, J.L.: Strong edge-coloring of graphs and applications to multi-$$k$$-gons. Ars Combin. 16A, 141\u2013150 (1983)","journal-title":"Ars Combin."},{"key":"2408_CR19","first-page":"399","volume-title":"Contemporary Methods in Graph Theory","author":"P Hor\u00e1k","year":"1990","unstructured":"Hor\u00e1k, P.: The strong chromatic index of graphs with maximum degree four. In: Rainer, B., Klaus, W. (eds.) Contemporary Methods in Graph Theory, pp. 399\u2013403. Wissenschaftsverlag, BI (1990)"},{"issue":"2","key":"2408_CR20","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1002\/jgt.3190170204","volume":"17","author":"P Hor\u00e1k","year":"1993","unstructured":"Hor\u00e1k, P., Qing, H., Trotter, W.T.: Induced matchings in cubic graphs. J Graph Theory 17(2), 151\u2013160 (1993)","journal-title":"J Graph Theory"},{"issue":"1","key":"2408_CR21","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7151\/dmgt.2003","volume":"38","author":"Z Hu","year":"2018","unstructured":"Hu, Z., Lih, K.-W., Liu, D.D.-F.: Upper bounds for the strong chromatic index of Halin graphs. Discuss. Math. Graph Theory 38(1), 5\u201326 (2018)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"3","key":"2408_CR22","doi-asserted-by":"publisher","first-page":"#P3.31","DOI":"10.37236\/7016","volume":"25","author":"M Huang","year":"2018","unstructured":"Huang, M., Santana, M., Yu, G.: Strong chromatic index of graphs with maximum degree four. Eectron. J. Combin. 25(3), #P3.31 (2018)","journal-title":"Eectron. J. Combin."},{"issue":"5","key":"2408_CR23","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1016\/j.disc.2016.10.016","volume":"340","author":"M Huang","year":"2017","unstructured":"Huang, M., Gexin, Y., Zhou, X.: The strong chromatic index of (3,$$\\delta$$)-bipartite graphs. Discret. Math. 340(5), 1143\u20131149 (2017)","journal-title":"Discret. Math."},{"key":"2408_CR24","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.disc.2014.02.002","volume":"324","author":"D Hud\u00e1k","year":"2014","unstructured":"Hud\u00e1k, D., Lu\u017ear, B., Sot\u00e1k, R., \u0160krekovski, R.: Strong edge-coloring of planar graphs. Discret. Math. 324, 41\u201349 (2014)","journal-title":"Discret. Math."},{"doi-asserted-by":"crossref","unstructured":"Hurley, E., de\u00a0Joannis\u00a0de Verclos, R., Kang, R.J.: An improved procedure for colouring graphs of bounded local density. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 135\u2013148. SIAM (2021)","key":"2408_CR25","DOI":"10.1137\/1.9781611976465.10"},{"doi-asserted-by":"crossref","unstructured":"Imrich, W., Klav\u017ear, S., Rall, D.F.: Topics in Graph Theory: Graphs and Their Cartesian Product. AK Peters\/CRC Press (2008)","key":"2408_CR26","DOI":"10.1201\/b10613"},{"key":"2408_CR27","doi-asserted-by":"publisher","first-page":"#R45","DOI":"10.37236\/963","volume":"14","author":"W Klotz","year":"2007","unstructured":"Klotz, W., Sander, T.: Some properties of unitary Cayley graphs. Electron. J. Combin. 14, #R45 (2007)","journal-title":"Electron. J. Combin."},{"issue":"9","key":"2408_CR28","doi-asserted-by":"publisher","first-page":"1536","DOI":"10.1016\/j.disc.2011.09.016","volume":"312","author":"Hsin-Hao Lai","year":"2012","unstructured":"Lai, H-H., Lih, K-W., Tsai, P-Y.: The strong chromatic index of Halin graphs. Discret. Math. 312(9), 1536\u20131541 (2012)","journal-title":"Discret. Math."},{"issue":"5","key":"2408_CR29","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1016\/j.aml.2011.10.046","volume":"25","author":"Ko-Wei Lih and Daphne Der-Fen Liu","year":"2012","unstructured":"Ko-Wei L., Daphne D-F.L: The strong chromatic index of cubic Halin graphs. Appl. Math. Lett. 25(5), 898\u2013901 (2012)","journal-title":"Appl. Math. Lett."},{"key":"2408_CR30","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.dam.2017.09.006","volume":"235","author":"J-B Lv","year":"2018","unstructured":"Lv, J.-B., Li, X., Gexin, Y.: On strong edge-coloring of graphs with maximum degree 4. Discret. Appl. Math. 235, 142\u2013153 (2018)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"2408_CR31","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(01)00237-2","volume":"118","author":"Mohammad Mahdian","year":"2002","unstructured":"Mahdian, M.: On the computational complexity of strong edge coloring. Discret. Appl. Math. 118(3), 239\u2013248 (2002)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"2408_CR32","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/jctb.1997.1724","volume":"69","author":"Michael Molloy","year":"1997","unstructured":"Molloy, M., Reed, B.: A bound on the strong chromatic index of a graph. J. Combin. Theory Ser B 69(2), 103\u2013109 (1997)","journal-title":"J. Combin. Theory Ser B"},{"issue":"2","key":"2408_CR33","doi-asserted-by":"publisher","first-page":"411","DOI":"10.7151\/dmgt.1456","volume":"29","author":"R Muthu","year":"2009","unstructured":"Muthu, R., Narayanan, N., Subramanian, C.R.: On $$k$$-intersection edge colourings. Discuss. Math. Graph Theory 29(2), 411\u2013418 (2009)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"16","key":"2408_CR34","doi-asserted-by":"publisher","first-page":"3726","DOI":"10.1016\/j.disc.2007.07.034","volume":"308","author":"K Nakprasit","year":"2008","unstructured":"Nakprasit, K.: A note on the strong chromatic index of bipartite graphs. Discret. Math. 308(16), 3726\u20133728 (2008)","journal-title":"Discret. Math."},{"issue":"1","key":"2408_CR35","first-page":"47","volume":"9","author":"Olivier Togni","year":"2007","unstructured":"Togni, O: Strong chromatic index of products of graphs. Discret. Math. Theor. Comput. Sci. 9(1), 47\u201356 (2007)","journal-title":"Discret. Math. Theor. Comput. Sci."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02408-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-021-02408-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02408-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T14:37:09Z","timestamp":1648046229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-021-02408-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,2]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["2408"],"URL":"https:\/\/doi.org\/10.1007\/s00373-021-02408-4","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2022,2,2]]},"assertion":[{"value":"19 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"51"}}