Star Coloring of Cartesian Product of Paths and Cycles

Abstract

A star coloring of an undirected graph $G$ is a proper vertex coloring of $G$ such that any path on four vertices in $G$ is not bicolored. The star chromatic number ${\chi }_s(G)$ of an undirected graph $G$ is the smallest integer $k$ for which $G$ admits a star coloring with $k$ colors. In this paper, the star chromatic numbers for some infinite subgraphs of Cartesian products of paths and cycles are established. In particular, we show that ${\chi }_s(P_i\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_j)=5$ for $i,j\ge 4$ and ${\chi }_s(C_i\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_j)=5$ for $i,j\ge 30$. We also show that ${\chi }_s(P_i\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_j\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_k)=6$ for $i,j,k\ge 4$, ${\chi }_s(C_3\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_3\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_k)=7$ for $k\ge 3$, and ${\chi }_s(C_{4i}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_{4j}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_{4k}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_{4l})\le 9$ for $i,j,k,l\ge 1$. Furthermore, we give the star chromatic numbers of $d$-dimensional hypercubes for $d\le 6$.