On star edge coloring of graphs

Abstract

This thesis primarily deals with star edge coloring of different families of graphs. A proper edge coloring is an assignment of colors to the edges of G so that no two adjacent edges receive the same color. The chromatic index of G, denoted by and#967; 0 (G), is the smallest integer k for which G admits a proper edge coloring with k colors. A star edge coloring is a proper edge coloring such that there is no bi-colored path of length four or a bi-colored cycle of length four. The name star comes from the vertex version where every pair of color classes induces a star forest. In a star edge coloring, every 2-colored connected subgraph of G is a path of length at most 3. The star chromatic index of a graph G, denoted by and#967; 0 s (G), is defined as the minimum k for which G admits a star edge coloring with k colors. In Chapter 1, we give basic definitions and literature survey on star edge coloring of graphs. In Chapter 2, we have determined an upper bound for the star chromatic index of the direct product of any two simple graphs G and H. We have also computed the star chromatic index of the direct product of (i) path Pm and path Pn and (ii) path Pm and star K1,n. In Chapter 3, we have determined upper bounds for the star chromatic index of Cartesian product and strong product of any two simple graphs G and H. We have also obtained upper bounds for the star chromate index of the Cartesian product of (i) tree T and path Pn, (ii) tree T and even cycle Cn and (iii) cycle Cm and cycle Cn. In 2013, Dvoand#711;rak´ et al proved that the star chromatic index of subcubic graphs lies between 4 and 7. There are cubic graphs like K4 with one subdivided edge, K3,3 and Heawood graph with the star chromatic index equal to 6. But there is no known example of a subcubic graph requiring 7 colors. Thus, Dvoand#711;rak´ et al conjectured that the star chromatic index of subcubic graphs is less than or equal to 6. In Chapter 4, we have studied the star edge coloring of subcubic graphs with maximum average degrees less than 11 5 and less than 8 3 . We have showed that the above conjecture holds good for such graphs. In Chapter 5, we have studied the star edge coloring of graphs with maximum degree and#8710; and#8805; 4 and maximum average degrees less than 8 3 and less than 14 5 . For these graphs, we have determined the star chromatic index in terms of the maximum degree of the graphs newline