Star Chromatic Index of Tensor Product of Graphs
P. Hemalatha *
Vellalar College for Women, Erode-12, India.
Shanmuga Vadivu D
Velalar College of Engineering and Technology, Erode-12, India.
*Author to whom correspondence should be addressed.
Abstract
A star edge coloring of a graph G is a proper edge coloring without bichromatic paths or cycles of length 4. The smallest
integer k such that G admits a star-edge-coloring with k colors is the star chromatic index of G and is denoted by \(x^\prime_{st}\) (G) . The tensor product of two graphs G and H, denoted by G×H is the graph with vertex set V(G)×V(H) and two vertices u = (u1,v1), v = (u2,v2) are adjacent in G×H if u1 is adjacent to u2 in G and v1 is adjacent to v2 in H. This paper focuses on determining the star chromatic index of Pm ×Cn and Cm×Cn and the obtained results are listed below.
(i) \(x^\prime_{st}\) (Pm×Cn) = 8, for m ≥ 7,n ≥ 7.
(ii) \(x^\prime_{st}\) (Cm×Cn) = 8 , for m ≥ 3,n ≥ 4.
The coloring technique is based on finding the star chromatic index of the maximal connected subgraph G1 in G such that χst (G) ≥ χst (G1).
Keywords: Paths, cycles, tensor product of graphs, star edge coloring, star chromatic index