page 3 : acyclic chromatic number – The \emph{acyclic chromatic number} of a graph $G = (V,E)$ is the smallest size of a vertex partition $P={V_1,\dots,V_\ell}$ such that each $V_i$ is an independent set and for all $V_i,V_j$ the graph $G[V_i \cup V_j]$ does not contain a cycle.
page 8 : maximum degree $k$ upper bounds acyclic chromatic number by $k^{\mathcal O(1)}$ – Lemma 4.6 ([15]). The acyclic chromatic number $\chi_a$ is uppre bounded by the maximum degree $\Delta$ (for every graph with $\Delta > 4$). We have $\chi_a \le \Delta(\Delta-1)/2$.
page 8 : h-index $k$ upper bounds acyclic chromatic number by $k^{\mathcal O(1)}$ – Lemma 4.7. The acyclic chromatic number $\chi_a$ is upper bounded by the $h$-index $h$. We have $\chi_a \le h(h+1)/2$.
page 8 : genus $k$ upper bounds acyclic chromatic number by $\mathcal O(k)$ – Lemma 4.8 ([3]). The accylic chromatic number $\chi_a$ is upper bounded by the genus $g$. We have $\chi_a \le 4g+4$.
page 8 : acyclic chromatic number $k$ upper bounds boxicity by $k^{\mathcal O(1)}$ – Lemma 4.9. The boxicity $b$ is upper bounded by the acyclic chromatic number $\chi_a$ (for every graph with $\chi_a>1$). We have $b \le \chi_a(\chi_a-1)$.
page 9 : acyclic chromatic number $k$ upper bounds degeneracy by $k^{\mathcal O(1)}$ – Lemma 4.18. The acyclic chromatic number $a$ upper bounds the degeneracy $d$. We have $d \le 2 \binom a2 - 1$
page 14 : book thickness $k$ upper bounds acyclic chromatic number by $2^{\mathcal O(k)}$ – Theorem 5. Acyclic chromatic number is bounded by stack-number (ed: a.k.a. book-thickness). In particular, every $k$-stack graph $G$ has acyclich chromatic number $\chi_a(G) \le 80^{k(2k-1)}$.
acyclic chromatic number – The acyclic chromatic number of a graph $G$ is the smallest size of a vertex partition $V_1,\dots,V_\ell$ such that each $V_i$ is an independent set and for all $i,j$ that graph $G[V_i \cup V_j]$ does not contain a cycle.
