A Brooks-Type Result for Sparse Critical Graphs

Alexandr Kostochka, Matthew Yancey

Research output: Contribution to journalArticlepeer-review


A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k-1)-colorable. Let fk(n) denote the minimum number of edges in an n-vertex k-critical graph. Recently the authors gave a lower bound, fk(n)≥⌈(k+1)(k−2)|V(G)|−k[k−3]2(k−1)⌉, that solves a conjecture by Gallai from 1963 and is sharp for every n≡1 (mod k-1). It is also sharp for k=4 and every n≤6. In this paper we refine the result by describing all n-vertex k-critical graphs G with |E(G)|≥(k+1)(k−2)|V(G)|−k(k−3)2(k−1). In particular, this result implies exact values of f5(n) for n≤7.

Original languageEnglish (US)
Pages (from-to)887-934
Number of pages48
Issue number4
StatePublished - Aug 1 2018

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'A Brooks-Type Result for Sparse Critical Graphs'. Together they form a unique fingerprint.

Cite this