Star coloring

☆ Save On Wikipedia ↗
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 ⁠ χ s ( G ) {\displaystyle \chi _{s}(G)} {\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 ⁠ d , {\displaystyle d,} {\displaystyle d,}⁠ the star chromatic number is ⁠ O ( d 3 / 2 ) . {\displaystyle O(d^{3/2}).} {\displaystyle O(d^{3/2}).}⁠ There exist graphs for which this bound is close to tight: they have star chromatic number ⁠ Ω ( d 3 / 2 / log 1 / 2 ⁡ n ) . {\displaystyle \Omega (d^{3/2}/\log ^{1/2}n).} {\displaystyle \Omega (d^{3/2}/\log ^{1/2}n).}⁠[5]

Complexity

It is NP-complete to determine whether χ s ( G ) ≤ 3 {\displaystyle \chi _{s}(G)\leq 3} {\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 q = 3 {\displaystyle q=3} {\displaystyle q=3} of q {\displaystyle q} {\displaystyle q}-centered coloring, colorings in which every connected subgraph either uses at least q {\displaystyle q} {\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 ⁠ χ a ( G ) {\displaystyle \chi _{a}(G)} {\displaystyle \chi _{a}(G)}⁠, we have that ⁠ χ a ( G ) ≤ χ s ( G ) {\displaystyle \chi _{a}(G)\leq \chi _{s}(G)} {\displaystyle \chi _{a}(G)\leq \chi _{s}(G)}⁠, and in fact every star coloring of G is an acyclic coloring. In the other direction, ⁠ χ s ( G ) ≤ 2 χ a ( G ) 2 − χ a ( G ) , {\displaystyle \chi _{s}(G)\leq 2\chi _{a}(G)^{2}-\chi _{a}(G),} {\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 χ p {\displaystyle \chi _{p}} {\displaystyle \chi _{p}} and the minimum number of colors in a ( p + 1 ) − c e n t e r e d {\displaystyle (p+1)-centered} {\displaystyle (p+1)-centered} coloring is Nešetřil & Ossona de Mendez (2012, p. 154, Corollary 7.1).

References