Star colorings and acyclic colorings (1973)

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 k such that G has an acyclic coloring [star coloring] with k colors.

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 P3 receiving only two colors is oriented toward the central vertex. A coloring of G is a star coloring if and only if it is an in-coloring of some orientation of G. Albertson et al. [ACKKR] prove many of their results using in-colorings, motivated by a similar idea in [NO].

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 Δ(G)?

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)≥k4/3-ε and conjectured that a(G)∈o(k²). Alon-McDiarmid-Reed [AMR] improved this to Ω((k4/log k)1/3) and proved an upper bound of O(k4/3), but no constructions with a(G) this larger are known. The problem is interesting for small values. Sharp bounds include a(G)≤Δ(G)+1 when 2≤Δ(G)≤4 (Burstein [Bu]).

Using in-colorings, [ACKKR] showed that χs(G)≤k²-k+2 when Δ(G)=k. This is not sharp, as they improve it to χs(G)≤7 when Δ(G)=3. Fertin-Raspaud-Reed [FRR] showed that χs(G)∈O(k3/2) and that there exist graphs with χs(G)∈Ω((k³/log k)1/2).

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 a(G)?

Comments: Grünbaum [G] noted without proof that χs(G) is bounded by a function of a(G). Fertin-Raspaud-Reed [FRR] proved that χs(G)≤a(G)2a(G)-1. [ACKKR] proved that χs(G)≤a(G)(2a(G)-1) and showed that this bound is optimal within a factor of about 4.

Question 3: What are the best bounds on χs(G) and a(G) for planar graphs with girth g?

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 10 and 20 [ACKKR]. The upper bound improves to 18 for girth at least 4 [NO] and to 16 for girth at least 5 [ACKKR], with examples requiring 6. For 6≤g≤9, planar graphs with girth g satisfy χs(G)≤14-g, and for 6≤g≤8 these are bounds on the list star chromatic number [KS]. Planar graphs with girth at least 13 are star 4-colorable [BCMRW], and this is sharp. For bipartite planar graphs, the star chromatic number can be as high as 8 and is at most 14 [KKT].

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(g2/3) for graphs embeddable on the orientable surface with g handles. Alon-Mohar-Sanders [AMS] improved this to O(g4/7).

Question 5: What is the best bound on χs(G) for graphs of genus g? What is the best bound for k-degenerate graphs?

Comments: [ACKKR] proves that χs(G)≤5g+20 for graphs with genus g. Also for each genus the star chromatic number is bounded by 4 when the girth is sufficiently large, and this is sharp. They also prove that χs(G)≤(2t+1) for graphs with tree-width t and construct chordal graphs to show that this is sharp. This yields the optimal upper bound of 6 for the star chromatic number of outerplanar graphs.

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 C5), complete p-partite graphs (n+1-α(G)), outerplanar graphs (at most 6, and 2-dimensional grids (equal to 5 for grids with at least four vertices in each direction). They also give bounds for χs(G) on planar graphs, d-dimensional hypercubes (between (d+3)/2 and d+2), d-dimensional grids, d-dimensional tori, graphs with bounded treewidth (weaker than [ACKKR]), and 3-regular graphs (weaker than [ACKKR]). For graphs with n vertices and m edges, they prove that χs(G)≥(2n+1-√γ)/2, where γ=4n(n-1)-8m+1 (actually, the argument holds also for a(G), and they have a typo in the statement of the result). They prove that the star chromatic number of the cartesian product of G and H is bounded by χs(G)χs(H).

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 P4'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 4-valent graph has an acyclic 5-coloring (in Russian). Soobshch. Akad. Nauk Gruzin. SSR 93 (1979), no. 1, 21--24.
[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.