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.
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$.