If $G$ is a finite, simple, undirected graph, its Hadwiger number $\eta(G)$ is the maximum integer $n$ such that $K_n$ is a minor of $G$. Given any integer $k>0$ let $E_k$ be the expected value of the value of $$\eta(G)-\chi(G),$$ where $V(G) = \{1,\ldots,k\}$, and $\chi(\cdot)$ denotes the chromatic number. An explicit formula for $E_k$ is given below. (Note: the Hadwiger conjecture, which is open, claims that $\eta(G) \geq \chi(G)$ for any finite graph.)
Is $\{E_k: k\in\mathbb{N}\}$ bounded? If no, what is an example of a non-decreasing function $f:\mathbb{N}\to\mathbb{N}$ such that $$0 < \lim\sup_{k\to\infty}\frac{E_k}{f(k)} < \infty$$?
EDIT. I forgot to mention the probability distribution, as commented below. Here's an explicit formula for $E_k$. Let $k\in\mathbb{N}$ be a positive integer, then let ${\cal G}_k$ be the set of all graphs on the vertex set $\{1,\ldots,k\}$. Then $$E_k = \frac{1}{|{\cal G}_k|}\sum_{G\in{\cal G}_k}(\eta(G) - \chi(G)).$$
