# Critical graphs with large minimum degree

A graph is said to be edge critical if the deletion of any edge decreases the chromatic number by $$1$$. Analogously, a graph is said to be vertex critical if the deletion of any vertex decreases the chromatic number by $$1$$. Here we use the convention that a critical graph means an edge critical graph.

A critical graph with chromatic number $$k$$ is said to be a $$k$$-critical graph. Similarly, a vertex critical graph with chromatic number $$k$$ is said to be a $$k$$-vertex-critical graph.

# A problem on critical graphs with large degree (proposed by Erdös [1] [2])

Let $$g(n,k)$$ denote the maximum value $$m$$ such that there exists a $$k$$-critical graph on $$n$$ vertices with minimum degree at least $$m$$. What is the magnitude of $$g(n,k)$$?
Is it true that $$g(n,4) \geq cn$$ for some constant $$c$$?

Simonovits [3] and Toft [4] proved that $$g(n,4) \geq c n^{1/3}$$.

As of 2011, there has been little progress on this problem.

Bibliography
1 P. Erdös, Problems and results on chromatic numbers in finite and infinite graphs, Graph theory with applications to algorithms and computer science (Kalamazoo, MI, 1984), Wiley-Intersci. Publ., 201-213, Wiley, New York, 1985.

2 P. Erdös, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., 397-406, Wiley, New York, 1991.

3 M. Simonovits, On colour-critical graphs, Studia Sci. Math. Hungar. 7 (1972), 67-81.

4 B. Toft, Two theorems on critical $$4$$-chromatic graphs, Studia Sci. Math. Hungar. 7 (1972), 83-89.