Strong edge coloring of Cayley graphs and some product graphs

DOI10.1007/S00373-021-02408-4zbMATH Open1484.05093arXiv2107.00718OpenAlexW3178956300MaRDI QIDQ2115170FDOQ2115170

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

Publication date: 15 March 2022

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

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$.

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

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

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)

Cites Work

• On the unitary Cayley graph of a finite ring
• Incidence and strong edge colorings of graphs
• A bound on the strong chromatic index of a graph
• Title not available (Why is that?)
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Induced matchings in bipartite graphs
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Title not available (Why is that?)
• Problems and results in combinatorial analysis and graph theory
• The strong chromatic index of a cubic graph is at most 10
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Title not available (Why is that?)
• The strong chromatic index of Halin graphs
• Induced matchings in cubic graphs
• A note on the strong chromatic index of bipartite graphs
• Upper bounds for the strong chromatic index of Halin graphs
• On cycles in the sequence of unitary Cayley graphs
• Some properties of unitary Cayley graphs
• A stronger bound for the strong chromatic index (extended abstract)
• Strong edge coloring sparse graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the strong chromatic index of cubic Halin graphs
• On the computational complexity of strong edge coloring
• On k-intersection edge colourings
• An extremal problem for sets with applications to graph theory
• Further results on strong edge-colourings in outerplanar graphs
• Strong edge-coloring of planar graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• Title not available (Why is that?)
• Strong chromatic index of graphs with maximum degree four
• Strong edge-coloring for jellyfish graphs
• On strong edge-coloring of graphs with maximum degree 4

Cited In (2)

• On strong edge-coloring of graphs with maximum degree 5
• Edge-colourings characterizing a class of Cayley graphs and a new characterization of hypercubes

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)