# Is the difference between the acyclic chromatic number and the star chromatic number unbounded?

Is $$\chi_s(G)-\chi_a(G)$$ unbounded in general graphs?

I thought $$\chi_s(G)-\chi_a(G)$$, the difference between the star chromatic number and the acyclic chromatic number, is unbounded for general graphs. But, I am unable to show this. I think I have seen a paper on star coloring which give $$\chi_a$$-binding functions for the star chromatic number and claim that these functions are best possible (but I don't recall the name of the paper; I think the paper dealt with a number of colouring variants including acyclic coloring and star coloring). If this is true, then $$\chi_s(G)-\chi_a(G)$$ must be unbounded.

Definitions
A coloring of a graph $$G$$ is a function $$f$$ from the vertex set of $$G$$ to a set of colors such that $$f(u)\neq f(v)$$ for every edge $$uv$$ of $$G$$. A coloring $$f$$ of $$G$$ is an acyclic coloring if there is no cycle in $$G$$ 2-colored by $$f$$. A coloring $$f$$ of $$G$$ is a star coloring if there is no 4-vertex path in $$G$$ 2-colored by $$f$$. The acyclic chromatic number $$\chi_a(G)$$ (resp. the star chromatic number $$\chi_s(G)$$) is the minimum number of colors required to acyclic color (resp. star color) the graph $$G$$.

• If you stumble on a paper discussing $\chi_a$-binding functions for the star chromatic number, the name of that paper would be enough for an answer. Jun 11 '21 at 6:46

Michael O. Albertson, Glenn G. Chappell, H. A. Kierstead, André Kündgen, Radhika Ramamurthi: Coloring with no $$2$$-colored $$P_4$$’s, Electronic Journal of Combinatorics 11 (2004), no. 1, art. no. R26, doi: 10.37236/1779.
They prove that $$\chi_s(G)\le\chi_a(G)\bigl(2\chi_a(G)-1\bigr)$$ (Corollary 4.6), and exhibit a family of graphs $$G_t$$ such that $$\chi_a(G_t)=t$$ and $$\chi_s(G_t)=\binom{t+1}2$$ (Theorem 6.3 and the comment below).
• Thanks. Interestingly, the graphs $G_t$ they construct are $(t-1)$-degenerate. Jun 11 '21 at 10:22