Strong edge coloring of Cayley graphs and some product graphs

DOI10.1007/S00373-021-02408-4MaRDI QIDQ2115170zbMATH OpenOpenAlexFDO

Authors Suresh Dara, Suchismita Mishra, Zsolt Tuza, N. Narayanan

Publication date 15 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.00718

zbMATH Keywords

Cayley graphproduct graphedge coloringstrong chromatic index

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph operations (line graphs, products, etc.) (05C76)

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 5 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by $4$.

Recommendations

• Strong chromatic index of products of graphs
• Strong chromatic index of \(K_{1, t}\)-free graphs
• Strong edge chromatic index of the generalized Petersen graphs
• Strong edge-coloring of strong product ${P_m}$ and ${P_n}$
• Strong chromatic index of unit distance graphs

Cites work

• scientific article; zbMATH DE number 3831957 (Why is no real title available?)
• scientific article; zbMATH DE number 4177085 (Why is no real title available?)
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 798645 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A bound on the strong chromatic index of a graph
• A note on the strong chromatic index of bipartite graphs
• A stronger bound for the strong chromatic index (extended abstract)
• An extremal problem for sets with applications to graph theory
• Further results on strong edge-colourings in outerplanar graphs
• Incidence and strong edge colorings of graphs
• Induced matchings in bipartite graphs
• Induced matchings in cubic graphs
• On \(k\)-intersection edge colourings
• On cycles in the sequence of unitary Cayley graphs
• On strong edge-coloring of graphs with maximum degree 4
• On the computational complexity of strong edge coloring
• On the strong chromatic index of cubic Halin graphs
• On the unitary Cayley graph of a finite ring
• Problems and results in combinatorial analysis and graph theory
• Some properties of unitary Cayley graphs
• Strong chromatic index of graphs with maximum degree four
• Strong chromatic index of products of graphs
• Strong edge coloring sparse graphs
• Strong edge-coloring for jellyfish graphs
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Strong edge-coloring of planar graphs
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• The strong chromatic index of Halin graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• The strong chromatic index of a cubic graph is at most 10
• Topics in graph theory. Graphs and their Cartesian product
• Upper bounds for the strong chromatic index of Halin graphs

Cited in

(3)

• Strong edge-coloring of strong product ${P_m}$ and ${P_n}$
• Edge-colourings characterizing a class of Cayley graphs and a new characterization of hypercubes
• On strong edge-coloring of graphs with maximum degree 5

This page was built for publication: Strong edge coloring of Cayley graphs and some product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115170)