Star coloring

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).

If we denote the acyclic chromatic number of a graph G by ⁠

The star chromatic number has been proved to be bounded on every proper minor closed class by Nešetřil & Ossona de Mendez (2003).

It was demonstrated by Albertson et al. (2004) that it is NP-complete to determine whether

Coleman & Moré (1984) showed that finding an optimal star coloring is NP-hard even when G is a bipartite graph.