**Originators:** Branko Grünbaum
(presented by Douglas West - REGS 2008)

**Definitions:**
An *acyclic coloring* of a graph *G* is a proper coloring such that
the union of any two color classes induces a forest. A *star coloring* of
*G* is a proper coloring such that the union of any two color classes
induces a forest whose components are stars. The *acyclic chromatic
number* [*star chromatic number*] of *G*, written *a(G)*
[*χ _{s}(G)*], is the minimum

**Background:**
Star colorings have two other natural equivalent descriptions. A star coloring
is a proper coloring in which every *4*-vertex path receives at least
three colors. Alternatively, define an *in-coloring* to be a proper
coloring of an orientation of *G* such that every copy of
*P _{3}* receiving only two colors is oriented toward the central
vertex. A coloring of

Note that always *χ(G)≤a(G)≤χ _{s}(G)*. Acyclic
coloring and star coloring were both introduced by Grunbaum [G].
Acyclic and star colorings have been studied primarily for planar graphs,
including for planar graphs with girth constraints, since on these families
there are absolute bounds. Nevertheless, the parameters are appealing to
study on other families and as related to other parameters such as maximum
degree and degeneracy.

**Question 1:**
What is the best possible upper bound on *a(G)* or
*χ _{s}(G)* in terms of

**Comments:**
For *a(G)*, Grünbaum [G] observed a quadratic upper bound and asked
whether *a(G)≤k+1* for graphs with maximum degree *k*.
Albertson-Berman [AB] reported that Erdős proved probabilistically the
existence of graphs with *a(G)≥k ^{4/3-ε}* and
conjectured that

Using in-colorings, [ACKKR] showed that
*χ _{s}(G)≤k²-k+2* when

Testing *a(G)≤3* is NP-complete, even for planar bipartite graphs
with degeneracy *2* (Kostochka [K]). Testing
*χ _{s}(G)≤3* is NP-complete
for planar bipartite graphs and for 3-colorable planar graphs [ACKKR].

**Question 2:**
What is the best bound on *χ _{s}(G)* in terms of

**Comments:**
Grünbaum [G] noted without proof that *χ _{s}(G)* is
bounded by a function of

**Question 3:**
What are the best bounds on *χ _{s}(G)* and

**Comments:**
Every planar graph is acyclically *5*-colorable (Borodin [B]). The upper
bound improves to *4* for girth at least *5* and to *3* for
girth at least *7* [BKW]. For *χ _{s}(G)*, the largest
value on planar graphs is between

**Conjecture 4:**
For every surface except the sphere and the Klein bottle, the largest values of
*a(G)* and *χ(G)* for graphs embeddable on the surface are the
same.

**Comments:**
Borodin conjectured that the sphere was the only exception, but
Mohar-Robertson-Sanders [MRS] provided also the Klein bottle. They proved
that *a(G)≤O(g ^{2/3})* for graphs embeddable on the orientable
surface with

**Question 5:**
What is the best bound on *χ _{s}(G)* for graphs of genus

**Comments:**
[ACKKR] proves that *χ _{s}(G)≤5g+20* for graphs with genus

**Question 6:**
What are the values of *a(G)* and *χ _{s}(G)* for other
natural families of graphs?

**Comments:**
Fertin-Raspaud-Reed [FRR] give the exact values of *χ _{s}(G)*
on trees (bounded by 1 plus the radius), cycles (3, except for

**References:**

[AB] Albertson, Michael O.; Berman, David M.; The acyclic chromatic number.
Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph
Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), pp.
51--69. Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976.

[ACKKR] Albertson, Michael O.; Chappell, Glenn G.; Kierstead, H. A.;
Kündgen, André; Ramamurthi, Radhika; Coloring with no 2-colored
*P _{4}*'s.
Electron. J. Combin. 11 (2004), Paper #R26, 13 pp.

[AMR] Alon, Noga; McDiarmid, Colin; Reed, Bruce; Acyclic coloring of graphs. Random Structures Algorithms 2 (1991), no. 3, 277--288.

[B] Borodin, O. V.; On acyclic colorings of planar graphs. Discrete Math. 25 (1979), no. 3, 211--236.

[BKW] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R.; Acyclic colourings of planar graphs with large girth. J. London Math. Soc. (2) 60 (1999), no. 2, 344--352.

[BCMRW] Y. Bu, D. Cranston, M. Montassier, A. Raspaud, W. Wang; Star coloring of sparse graphs, manuscript.

[Bu] Buršteĭn, M. I. Every

[FRR] Fertin, Guillaume; Raspaud, André; Reed, Bruce; Star coloring of graphs. J. Graph Theory 47 (2004), no. 3, 163--182.

[G] Grünbaum, Branko; Acyclic colorings of planar graphs. Israel J. Math. 14 (1973), 390--408.

[KKT] Kierstead, H.A.; Kündgen, A.; Timmons, C.; Journal of Graph Theory, 60 (2009), 1-10.

[K] Kostochka, A.V.; Upper bounds of chromatic functions of graphs (in Russian). Doctoral these, Novosibirsk, 1978.

[KS] Kündgen, André; Timmons, Craig; Star coloring planar graphs from small lists, submitted.

[MRS] B. Mohar, N. Robertson, and D.P. Sanders, On acyclic colorings of graphs on surfaces, unpublished manuscript, 1994.

[NO] Nešetřil, Jaroslav; Ossona de Mendez, Patrice; Colorings and homomorphisms of minor closed classes. Discrete and computational geometry, 651--664, Algorithms Combin., 25, Springer, Berlin, 2003.