Star Coloring of the Cartesian Product of Cycles

Abstract

A proper vertex coloring of a graph $G$ is called a star coloring if every two color classes induce a forest whose each component is a star, which means there is no bicolored $P_4$ in $G$. In this paper, we show that the Cartesian product of any two cycles, except $C_3\square C_3$ and $C_3\square C_5$, has a $5$-star coloring.

12 pages, 6 figures