Star coloring

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 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. Star coloring has been introduced by Grünbaum (1973). The star chromatic number ⁠$\chi _{s}(G)$⁠ of G is the fewest 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.

The star chromatic number has been proved to be bounded on every proper minor closed class by Nešetřil & Ossona de Mendez (2003). This results was further generalized by Nešetřil & Ossona de Mendez (2006) 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 Albertson et al. (2004) that it is NP-complete to determine whether $\chi _{s}(G)\leq 3$, even when G is a graph that is both planar and bipartite. Coleman & Moré (1984) showed that finding an optimal star coloring is NP-hard even when G is a bipartite graph.

References

• Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika (2004), "Coloring with no 2-Colored P₄'s", The Electronic Journal of Combinatorics, 11 (1), doi:10.37236/1779, MR 2056078.
• Coleman, Thomas F.; Moré, Jorge (1984), "Estimation of sparse Hessian matrices and graph coloring problems" (PDF), Mathematical Programming, 28 (3): 243–270, doi:10.1007/BF02612334, hdl:1813/6374, MR 0736293.
• Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory, 47 (3): 163–182, doi:10.1002/jgt.20029, MR 2089462.
• Grünbaum, Branko (1973), "Acyclic colorings of planar graphs", Israel Journal of Mathematics, 14 (4): 390–408, doi:10.1007/BF02764716, MR 0317982.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2003), "Colorings and homomorphisms of minor closed classes", Discrete & Computational Geometry: The Goodman-Pollack Festschrift, Algorithms & Combinatorics, vol. 25, Springer-Verlag, pp. 651–664, MR 2038495.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2006), "Tree depth, subgraph coloring and homomorphism bounds", European Journal of Combinatorics, 27 (6): 1022–1041, doi:10.1016/j.ejc.2005.01.010, MR 2226435.

External links

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