Ore's Conjecture for k=4 and Gr otzsch Theorem

Original · EN

A graph G is k- critical if it has chromatic number k, but every proper subgraph of G is (k-1)--colorable. Let fₖ(n) denote the minimum number of edges in an n-vertex k-critical graph. In a very recent paper, we gave a lower bound, fₖ(n) ≥ F(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 the conjecture by Ore from 1967 that for every k≥ 4 and n≥ k+2, fₖ(n+k-1)=f(n)+k-1/2(k - 2/k-1). We also show that our result implies a simple short proof of the Gr otzsch Theorem that every triangle-free planar graph is 3-colorable.