Star coloring

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.^[1] Star coloring has been introduced by Grünbaum (1973).^[2] The star chromatic number ⁠${\displaystyle \chi _{s}(G)}$⁠ of G is the fewest colors needed to star color G.

Grünbaum (1973) observed that the star chromatic number is bounded for planar graphs.^[2] More precisely, the star chromatic number of planar graphs is at most 20, and some planar graphs have star chromatic number at least 10.^[1] More generally, the star chromatic number is bounded on every proper minor closed class.^[3] This result has been generalized to all low-tree-depth colorings (standard coloring and star coloring being low-tree-depth colorings with respective parameter 1 and 2).^[4]

For every graph of maximum degree ⁠${\displaystyle d,}$⁠ the star chromatic number is ⁠${\displaystyle O(d^{3/2}).}$⁠ There exist graphs for which this bound is close to tight: they have star chromatic number ⁠${\displaystyle \Omega (d^{3/2}/\log ^{1/2}n).}$⁠^[5]

It is NP-complete to determine whether ${\displaystyle \chi _{s}(G)\leq 3}$, even when G is a graph that is both planar and bipartite.^[1] Finding an optimal star coloring is NP-hard even when G is a bipartite graph.^[6]

Star coloring is the special case for ${\displaystyle q=3}$ of ${\displaystyle q}$-centered coloring, colorings in which every connected subgraph either uses at least ${\displaystyle q}$ colors or has at least one color that is used for exactly one vertex. For such a coloring, a connected subgraph with only two colors must be a star, with the vertex of a unique color at its center. There can be no edges between the remaining vertices in the component, because they would form two-vertex connected subgraphs without a uniquely used color.^[7]

Another 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 ⁠${\displaystyle \chi _{a}(G)}$⁠, we have that ⁠${\displaystyle \chi _{a}(G)\leq \chi _{s}(G)}$⁠, and in fact every star coloring of G is an acyclic coloring. In the other direction, ⁠${\displaystyle \chi _{s}(G)\leq 2\chi _{a}(G)^{2}-\chi _{a}(G),}$⁠ so each of the two kinds of chromatic number is bounded if and only if the other one is.^[1]

• 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.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058

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