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$?



Minimal degree in a critical graph
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
> 
> 
> 


