Suppose you want to have a graph with chromatic number equaling some value , such that is minimal with this property. So you end up with a -(vertex-)critical graph.

It is easy to construct critical graphs by starting with some easy-to-verify example like and then adding points and connecting them to all the vertices already present. But the graphs you get are highly non-regular: some vertices have quite low degree, and the one vertex you added has maximum degree.

I was wondering where the limits for regularity for -critical graphs are. Here’s an attempt to make this a bit more formal:

For a finite, simple, undirected graph let and denote the minimum and maximum degree of , respectively.

Is there a global constant such that whenever are integers with and , there is a -vertex critical graph with and ?

I asked this question on MathOverflow a while ago, but it has not been answered yet.