In the mathematical field of graph theory, a star coloring of a graph 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. Star coloring has been introduced by .The star chromatic number of is the fewest colors needed to star color .
One generalization of star coloring is the closely related concept of acyclic coloring, where it is required that every cycle uses at least three colors, so the two-color induced subgraphs are forests. If we denote the acyclic chromatic number of a graph by, we have that, and in fact every star coloring of is an acyclic coloring.
The star chromatic number has been proved to be bounded on every proper minor closed class by . This results was further generalized by to all low-tree-depth colorings (standard coloring and star coloring being low-tree-depth colorings with respective parameter 1 and 2).
It was demonstrated by that it is NP-complete to determine whether
\chis(G)\leq3