Critical Graphs with few Edges
摘要
This chapter is concerned with the minimum number ext(k,n) of edges in k-critical graphswith n vertices. Brooks’ theorem says that 2ext(k,n) ≥ (k −1)n+1 forn > k ≥ 4. That it is worthwhile to study critical graphs, and especially the function ext(k,n), was first emphasized by G. A. Dirac in his thesis, and subsequently by T. Gallai and O. Ore. In 2014, A. V. Kostochka and M.