Find the exact maximum number of edges for a \(k\)-critical graph on n vertices

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.

Problem (1949)

What is the largest number \(m\), denoted by \(f(n,k)\), such that there is a \(k\)-critical graph on \(n\) vertices and \(m\) edges? In particular, determine \[ \lim_{n \rightarrow \infty} \frac{f(n,k)}{n^2} = c_k. \]

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.