Ore's conjecture for k=4 and Grötzsch's Theorem

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. In a very recent paper, we gave a lower bound, fk(n)≥(k, n), that is sharp for every n≡1 (mod k-1). It is also sharp for k=4 and every n≥6. In this note, we present a simple proof of the bound for k=4. It implies the case k=4 of two conjectures: Gallai in 1963 conjectured that if n≡1 (mod k-1) then (Formula presented), and Ore in 1967 conjectured that for every k≥4 and (Formula presented). We also show that our result implies a simple short proof of Grötzsch's Theorem that every triangle-free planar graph is 3-colorable.

Original languageEnglish (US)
Pages (from-to)323-329
Number of pages7
Issue number3
StatePublished - Jun 2014

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Ore's conjecture for k=4 and Grötzsch's Theorem'. Together they form a unique fingerprint.

Cite this