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).
Complexity
It was demonstrated by that it is NP-complete to determine whether , even when G is a graph that is both planar and bipartite. showed that finding an optimal star coloring is NP-hard even when G is a bipartite graph.
References
. . . . . .
External links
Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008.