Star coloring

This article is about a topic in the mathematics of graph coloring. For the colors of stars in astronomy, see Stellar classification.

The star chromatic number of the Dyck graph is 4, although its 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. ^[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.

In special classes of graphs

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]

Complexity

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]

Related concepts

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]

Notes

1. Albertson et al. (2004).
2. Grünbaum (1973), p. 406, remark 12(i).
3. Nešetřil & Ossona de Mendez (2003).
4. Nešetřil & Ossona de Mendez (2006).
5. Fertin, Raspaud & Reed (2004).
6. Coleman & Moré (1984).
7. Nešetřil & Ossona de Mendez (2012 , p. 150). The equivalence between the numbers denoted here as ${\displaystyle \chi _{p}}$ and the minimum number of colors in a ${\displaystyle (p+1)-centered}$ coloring is Nešetřil & Ossona de Mendez (2012 , p. 154, Corollary 7.1).

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 .
• 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

External links

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