A star coloring of a graph G is a proper vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. A graph G is k- star-colorable if there exists a star coloring of G from a set of k colors. The minimum positive integer k for which G is k-star-colorable is the star chromatic number of G and is denoted by s(G). In this paper, upper and lower bounds are presented for the star chromatic number of the rooted product, hierarchical product, and lexicographic product.

Keywords