Star coloring
In the mathematical field of graph theory, a star coloring of a graph Template:Mvar 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 Template:Harvtxt. The star chromatic number Template:Tmath of Template:Mvar is the fewest colors needed to star color Template:Mvar.
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 Template:Mvar by Template:Tmath, we have that Template:Tmath, and in fact every star coloring of Template:Mvar is an acyclic coloring.
The star chromatic number has been proved to be bounded on every proper minor closed class by Template:Harvtxt. This results was further generalized by Template:Harvtxt 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 Template:Harvtxt that it is NP-complete to determine whether , even when G is a graph that is both planar and bipartite. Template:Harvtxt showed that finding an optimal star coloring is NP-hard even when G is a bipartite graph.
References
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
External links
- Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008.