How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph?
Hint: It's better to prove that if $mad(G) \leq k$ and no induced subgraph of $G$ is $k$-regular then $\chi(G) \leq k$. Here is the idea of the proof:


Show that $G$ has a vertex $v$ of degree smaller than $k$.
Color $G - v$ using $k$ colors (by induction).
Complete this to a $k$-coloring of $G$.