Star coloring

File:Graph star coloring.svg

The star chromatic number of Dyck graph is 4, while the chromatic number is 2.

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 . 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 . 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 ${\chi }_s(G)\le 3$, 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.