A new lower bound on the number of edges in colour-critical graphs and hypergraphs

A graph G is called k-critical if it has chromatic number k, but every proper subgraph of G is (k−1)-colourable. We prove that every k-critical graph (k⩾6) on n⩾k+2 vertices has at least 12 (k−1+k−3(k−c)(k−1)+k−3)n edges where c=(k−5)(12−1(k−1)(k−2)). This improves earlier bounds established by Gallai (Acad. Sci. 8 (1963) 165) and by Krivelevich (Combinatorica 17 (1999) 401).