A Brooks-Type Result for Sparse Critical Graphs

A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k-1)-colorable. Let f(k)(n) denote the minimum number of edges in an n-vertex k-critical graph. Recently the authors gave a lower bound, , that solves a conjecture by Gallai from 1963 and is sharp for every n1 (mod k-1). It is also sharp for k=4 and every n6. In this paper we refine the result by describing all n-vertex k-critical graphs G with <. In particular, this result implies exact values of f(5)(n) for n >= 7.