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.