Journal
GRAPHS AND COMBINATORICS
Volume 38, Issue 2, Pages -Publisher
SPRINGER JAPAN KK
DOI: 10.1007/s00373-021-02408-4
Keywords
Edge coloring; Strong chromatic index; Cayley graph; Product graph
Categories
Funding
- ELKH Alfred Renyi Institute of Mathematics
- Szechenyi 2020 programme [EFOP-3.6.1-16-2016-00015]
- National Research, Development and Innovation Office - NKFIH [SNN 129364]
Ask authors/readers for more resources
This paper investigates the strong chromatic index of unitary Cayley graphs and determines its exact value. Additionally, it provides bounds for the strong chromatic index of the Cartesian product of two trees and the product of a tree with a cycle.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available