Star coloring of graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic number of an undirected graph G, denoted by χ_s(G), is the smallest integer k for which G admits a star coloring with k colors. In this paper, we give the exact value of the star chromatic number of different families of graphs such as trees, cycles, complete bipartite graphs, outerplanar graphs, and 2‐dimensional grids. We also study and give bounds for the star chromatic number of other families of graphs, such as planar graphs, hypercubes, d‐dimensional grids (d ≥ 3), d‐dimensional tori (d ≥ 2), graphs with bounded treewidth, and cubic graphs. We end this study by two asymptotic results, where we prove that, when d tends to infinity, (i) there exist graphs G of maximum degree d such that $\chi _s(G) = \Omega({d^{{3\over 2}}\backslash ({\rm log}\ {d})^{1\over 2}})$ and (ii) for any graph G of maximum degree d, $\chi _s(G) = O({d^{{3\over 2}}})$ . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 163–182, 2004