Minimal degree in a critical graph We say that a finite, simple, undirected graph $G=(V,E)$ is $k$-critical for $k\in\mathbb{N}$ if $\chi(G)=k$ and $\chi(G\setminus \{v\}) = k-1$ for all $v\in V(G)$. Let $\delta(G)$ denote the minimum degree of $G$.
It is easy to see that $\delta(G)\geq k-1$ for any $k$-critical graph $G$.
Is there a global constant $n_0\in \mathbb{N}$ such that if $G$ is $k$-critical, then $\delta(G) \leq k + n_0$?
 A: The only $2$-critical graph is $K_2$ and the only $3$-critical graphs are odd cycles, therefore the answer is yes for $k\in \{2,3\}$. For $k\geq 4$ the answer is no.
Let's start with the easy case, $k\geq 6$. The Dirac construction of critical graphs starts with two graphs $G_1$ which is $k_1$-critical, and $G_2$ which is $k_2$-critical and forms a third graph by taking their disjoint union together with all the edges that connect a vertex in $G_1$ to a vertex in $G_2$. This graph is $k_1+k_2$ critical. So pick some large $n$, pick two graphs on $n/2$ vertices which are both $k/2$-critical and join them as above. This shows that the minimum degree is not only unbounded, but it can grow linearly in the number of vertices! (Here we used $k\geq 6$ because we needed the existence of $k/2$-critical graphs with arbitrarily large number of vertices.)
The situation for $k=4,5$ is a little more complicated. It is known that the minimum degree doesn't have to be bounded. In fact the papers below have constructions showing that it can grow as $|V(G)|^{1/3}$, but the exact optimal growth rate is unknown.

M. Simonovits, "On colour-critical graphs", Studia Sci. Math. Hungar. 7 (1972), 67-81.
B. Toft, "Two theorems on critical 4-chromatic graphs", Studia Sci. Math. Hungar. 7 (1972), 83-89

