Star Coloring of Tensor Product of Two Graphs

A star coloring of a graph Formula: see text is a proper vertex coloring such that no path on four vertices is bicolored. The smallest integer Formula: see text for which Formula: see text admits a star coloring with Formula: see text colors is called the star chromatic number of Formula: see text, denoted by Formula: see text. In this paper, we study the star coloring of the tensor product of two graphs and obtain the following results. 1. We give an upper bound on the star chromatic number of the tensor product of two arbitrary graphs. 2. We determine the exact value of the star chromatic number of the tensor product of two paths. 3. We show that the star chromatic number of the tensor product of two cycles is five, except for Formula: see text and Formula: see text. 4. We give tight bounds for the star chromatic number of the tensor product of a cycle and a path.