Strong Edge coloring of Cayley graphs and some product graphs

Show simple item record Dara, Suresh Mishra, Suchismita Narayanan, Narayanan Tuza, Zsolt
dc.coverage.spatial United Kingdom 2022-02-16T08:48:06Z 2022-02-16T08:48:06Z 2022-04
dc.identifier.citation Dara, Suresh; Mishra, Suchismita; Narayanan Narayanan and Tuza, Zsolt, "Strong Edge coloring of Cayley graphs and some product graphs", Graphs and Combinatorics, DOI: 10.1007/s00373-021-02408-4, vol. 38, no. 2, Apr. 2022 en_US
dc.identifier.issn 0911-0119
dc.identifier.issn 1435-5914
dc.description.abstract A strong edge coloring of a graph G is a proper edge coloring of G 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.
dc.description.statementofresponsibility by Suresh Dara, Suchismita Mishra, Narayanan Narayanan and Zsolt Tuza
dc.format.extent vol. 38, no. 2
dc.language.iso en_US en_US
dc.publisher Springer en_US
dc.subject Edge coloring en_US
dc.subject Strong chromatic index en_US
dc.subject Cayley graph en_US
dc.subject Product graph en_US
dc.title Strong Edge coloring of Cayley graphs and some product graphs en_US
dc.type Article en_US
dc.relation.journal Graphs and Combinatorics

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account