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 \Box C_j) = 5\) for \(i, j \geq 4\) and \(\chi_s(C_i \Box C_j) = 5\) for \(i, j \geq 30\). We also show that \(\chi_s(P_i \Box P_j \Box P_k) = 6\) for \(i, j, k \geq 4\), \(\chi_s(C_{3} \Box C_{3} \Box C_k) = 7\) for \(k \geq 3\), and \(\chi_s(C_{4i} \Box C_{4j} \Box P_{4k} \Box C_{4l}) \leq 9\) for \(i, j, k, l \geq 1\). Furthermore, we give the star chromatic numbers of \(d\)-dimensional hypercubes for \(d \leq 6\).