{{short description|Graph coloring avoiding 2-colored paths}} {{about|a topic in the mathematics of graph coloring|the colors of stars in astronomy|Stellar classification}} [[Image:Graph star coloring.svg|thumb|right|300px|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 {{mvar|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.{{sfnp|Albertson|Chappell|Kierstead|Kündgen|2004}} Star coloring has been introduced by {{harvtxt|Grünbaum|1973}}.{{sfnp|Grünbaum|1973|loc=remark 12(i)|page=406}} The '''star chromatic number''' {{tmath|\chi_s(G)}} of {{mvar|G}} is the fewest colors needed to star color {{mvar|G}}.
==In special classes of graphs== {{harvtxt|Grünbaum|1973}} observed that the star chromatic number is bounded for planar graphs.{{sfnp|Grünbaum|1973|loc=remark 12(i)|page=406}} More precisely, the star chromatic number of planar graphs is at most 20, and some planar graphs have star chromatic number at least 10.{{sfnp|Albertson|Chappell|Kierstead|Kündgen|2004}} More generally, the star chromatic number is bounded on every proper minor closed class.{{sfnp|Nešetřil|Ossona de Mendez|2003}} 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).{{sfnp|Nešetřil|Ossona de Mendez|2006}}
For every graph of maximum degree {{tmath|d,}} the star chromatic number is {{tmath|O(d^{3/2}).}} There exist graphs for which this bound is close to tight: they have star chromatic number {{tmath|\Omega(d^{3/2}/\log^{1/2} n).}}{{sfnp|Fertin|Raspaud|Reed|2004}}
== Complexity == It is NP-complete to determine whether <math>\chi_s(G) \leq 3</math>, even when ''G'' is a graph that is both planar and bipartite.{{sfnp|Albertson|Chappell|Kierstead|Kündgen|2004}} Finding an optimal star coloring is NP-hard even when ''G'' is a bipartite graph.{{sfnp|Coleman|Moré|1984}}
==Related concepts== Star coloring is the special case for <math>q=3</math> of <math>q</math>-centered coloring, colorings in which every connected subgraph either uses at least <math>q</math> 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.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012|p=150}}. The equivalence between the numbers denoted here as <math>\chi_p</math> and the minimum number of colors in a <math>(p+1)-centered</math> coloring is {{harvtxt|Nešetřil|Ossona de Mendez|2012|loc=Corollary 7.1|p=154}}.</ref>
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 {{mvar|G}} by {{tmath|\chi_a(G)}}, we have that {{tmath|\chi_a(G) \leq \chi_s(G)}}, and in fact every star coloring of {{mvar|G}} is an acyclic coloring. In the other direction, {{tmath|\chi_s(G)\le 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.{{sfnp|Albertson|Chappell|Kierstead|Kündgen|2004}}
==Notes== {{reflist}}
== References == *{{citation | last1 = Albertson | first1 = Michael O. | last2 = Chappell | first2 = Glenn G. | last3 = Kierstead | first3 = Hal A. | last4 = Kündgen | first4 = André | last5 = Ramamurthi | first5 = Radhika | url = https://www.combinatorics.org/Volume_11/Abstracts/v11i1r26.html | mr = 2056078 | title = Coloring with no 2-Colored ''P''<sub>4</sub>'s | journal = The Electronic Journal of Combinatorics | volume = 11 | issue = 1 | year = 2004| doi = 10.37236/1779 | doi-access = free }}. *{{citation | last1 = Coleman | first1 = Thomas F. | author1-link = Thomas F. Coleman | last2 = Moré | first2 = Jorge | mr = 0736293 | title = Estimation of sparse Hessian matrices and graph coloring problems | journal = Mathematical Programming | volume = 28 | issue = 3 | pages = 243–270 | year = 1984 | doi = 10.1007/BF02612334 | doi-access=free| url = https://ecommons.cornell.edu/bitstream/1813/6374/1/82-535.pdf| hdl = 1813/6374 | hdl-access = free }}. *{{citation | last1 = Fertin | first1 = Guillaume | last2 = Raspaud | first2 = André | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician) | journal = Journal of Graph Theory | title = Star coloring of graphs | volume = 47 | issue = 3 | pages = 163–182 | year = 2004 | mr = 2089462 | doi = 10.1002/jgt.20029| url = https://hal.archives-ouvertes.fr/hal-00307788 }}. *{{citation | last = Grünbaum | first = Branko | authorlink=Branko Grünbaum | doi = 10.1007/BF02764716 | doi-access= | mr = 0317982 | journal = Israel Journal of Mathematics | title = Acyclic colorings of planar graphs | volume = 14 | pages = 390–408 | year = 1973| issue = 4 }}. * {{citation | first1 = Jaroslav | last1 = Nešetřil | authorlink1=Jaroslav Nešetřil | first2 = Patrice | last2 = Ossona de Mendez | author2-link = Patrice Ossona de Mendez | mr = 2038495 | series = Algorithms & Combinatorics | publisher = Springer-Verlag | volume = 25 | pages = 651–664 | contribution = Colorings and homomorphisms of minor closed classes | title = Discrete & Computational Geometry: The Goodman-Pollack Festschrift | year = 2003}}. * {{citation | first1 = Jaroslav | last1 = Nešetřil | authorlink1=Jaroslav Nešetřil | first2 = Patrice | last2 = Ossona de Mendez | author2-link = Patrice Ossona de Mendez | doi = 10.1016/j.ejc.2005.01.010 | mr = 2226435 | journal = European Journal of Combinatorics | volume = 27 | issue = 6 | pages = 1022–1041 | title = Tree depth, subgraph coloring and homomorphism bounds | year = 2006| doi-access = }}. *{{citation | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | doi = 10.1007/978-3-642-27875-4 | isbn = 978-3-642-27874-7 | mr = 2920058 | publisher = Springer | series = Algorithms and Combinatorics | title = Sparsity: Graphs, Structures, and Algorithms | volume = 28 | year = 2012}}
== External links == * [http://www.math.uiuc.edu/~west/regs/starcol.html Star colorings and acyclic colorings (1973)], present at the [http://www.math.uiuc.edu/~west/regs/ Research Experiences for Graduate Students (REGS)] at the University of Illinois, 2008.
Category:Graph coloring Category:NP-complete problems