Star coloring

In graph-theoretic mathematics, 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. The star chromatic number $\chi _{s}(G)$ of G is the least number of colors needed to star color G.

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 G by $\chi _{a}(G)$, we have that $\chi _{a}(G)\leq \chi _{s}(G)$, and in fact every star coloring of G is an acyclic coloring.

References

• Coleman, Thomas F.; Cai, Jin-Yi (1986), "The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices", SIAM. J. on Algebraic and Discrete Methods, 7 (2): 221–235, doi:10.1137/0607026.

• Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory, 47 (3): 163–182, doi:10.1002/jgt.20029.

External links

• Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008.