Strong Edge Coloring of Cayley Graphs and Some Product Graphs

被引：0
作者：
Suresh Dara
Suchismita Mishra
Narayanan Narayanan
Zsolt Tuza
机构：
[1] VIT Bhopal University,Department of Mathematics, School of Advanced Sciences
[2] Indian Institute of Technology Gandhinagar,Computer Science and Engineering
[3] Indian Institute of Technology Madras,Department of Mathematics
[4] Budapest & University of Pannonia,Alfréd Rényi Institute of Mathematics
来源：
Graphs and Combinatorics | 2022年 / 38卷
关键词：
Edge coloring; Strong chromatic index; Cayley graph; Product graph; 05C15; 05C76; 05C05;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
相关论文
共 66 条
[1]  
Akhtar R(2009)On the unitary Cayley graph of a finite ring Electron. J. Combin. 16 #R117-89
[2]  
Boggess M(1985)An extremal problem for sets with applications to graph theory J. Combin. Theory Ser A 40 82-252
[3]  
Jackson-Henderson T(1992)The strong chromatic index of a cubic graph is at most 10 Discret. Math. 108 231-778
[4]  
Karpman R(2015)Bonamy, Marthe, Hocquard, Hervé: Strong edge coloring sparse graphs Electron. Notes Discret. Math. 49 773-3
[5]  
Jiménez I(2004)On cycles in the sequence of unitary cayley graphs Discret. Math. 282 1-44
[6]  
Kinzel A(2015)Montero, Leandro, Narayanan, Narayanan: Further results on strong edge-colourings in outerplanar graphs Australas. J. Combin. 62 35-58
[7]  
Pritikin D(1993)Incidence and strong edge colorings of graphs Discret. Math. 122 51-284
[8]  
Alon Noga(2015)Joos, Felix: A stronger bound for the strong chromatic index Electron. Notes Discret. Math. 49 277-2355
[9]  
Andersen Lars Døvling(2015)Strong edge-coloring for jellyfish graphs Discret. Math. 338 2348-135
[10]  
Bensmail Julien(1990)The maximum number of edges in Discret. Math. 81 129-2778
1234567