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$
degeneracy – … the least $k$ for which there exists an ordering of the vertices of $G$ in which each vertex has fewer than $k$ neighbors that are earlier in the ordering.
degeneracy $k$ upper bounds chromatic number by $\mathcal O(k)$ – Greedily color the vertices in order of the degeneracy ordering. As each vertex has at most $k$ colored predecesors we use at most $k+1$ colors.
degeneracy $k$ upper bounds average degree by $\mathcal O(k)$ – Removing a vertex of degree $d$ increases the value added to the sum of all degrees by at most $2d$, hence, the average is no more than twice the degeneracy.
