Star coloring

Grünbaum (1973) observed that the star chromatic number is bounded for planar graphs.^[2] More precisely, the star chromatic number of planar graphs is at most 20, and some planar graphs have star chromatic number at least 10.^[1] More generally, the star chromatic number is bounded on every proper minor closed class.^[3] This result has been generalized to all low-tree-depth colorings (standard coloring and star coloring being low-tree-depth colorings with respective parameter 1 and 2).^[4]

For every graph of maximum degree ⁠${\displaystyle d,}$⁠ the star chromatic number is ⁠${\displaystyle O(d^{3/2}).}$⁠ There exist graphs for which this bound is close to tight: they have star chromatic number ⁠${\displaystyle \Omega (d^{3/2}/\log ^{1/2}n).}$⁠^[5]

It is NP-complete to determine whether ${\displaystyle \chi _{s}(G)\leq 3}$, even when G is a graph that is both planar and bipartite.^[1] Finding an optimal star coloring is NP-hard even when G is a bipartite graph.^[6]

Star coloring is the special case for ${\displaystyle q=3}$ of ${\displaystyle q}$-centered coloring, colorings in which every connected subgraph either uses at least ${\displaystyle q}$ colors or has at least one color that is used for exactly one vertex. For such a coloring, a connected subgraph with only two colors must be a star, with the vertex of a unique color at its center. There can be no edges between the remaining vertices in the component, because they would form two-vertex connected subgraphs without a uniquely used color.^[7]

Another 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 G by ⁠${\displaystyle \chi _{a}(G)}$⁠, we have that ⁠${\displaystyle \chi _{a}(G)\leq \chi _{s}(G)}$⁠, and in fact every star coloring of G is an acyclic coloring. In the other direction, ⁠${\displaystyle \chi _{s}(G)\leq 2\chi _{a}(G)^{2}-\chi _{a}(G),}$⁠ so each of the two kinds of chromatic number is bounded if and only if the other one is.^[1]