Star coloring

Summary

In the mathematical field of graph theory, a star coloring of a graph $G$ 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 (Grünbaum 1973). The star chromatic number $\chi_s(G)$ of $G$ is the fewest colors needed to star color $G$.