Ore's conjecture on color-critical graphs is almost true

Alexandr Kostochka, Matthew Yancey

Research output: Contribution to journalArticle

Abstract

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. We give a lower bound, fk(n)≥F(k, n), that is sharp for every n=1(modk-1). The bound is also sharp for k=4 and every n≥6. The result improves a bound by Gallai and subsequent bounds by Krivelevich and Kostochka and Stiebitz, and settles the corresponding conjecture by Gallai from 1963. It establishes the asymptotics of fk(n) for every fixed k. It also proves that the conjecture by Ore from 1967 that for every k≥4 and n≥k+2, fk(n+k-1)=fk(n)+k-12(k-2k-1) holds for each k≥4 for all but at most k3/12 values of n. We give a polynomial-time algorithm for (k-1)-coloring of a graph G that satisfies |E(G[W])|<F(k, |W|) for all W⊆V(G), |W|≥k. We also present some applications of the result.

Original languageEnglish (US)
Pages (from-to)73-101
Number of pages29
JournalJournal of Combinatorial Theory. Series B
Volume109
DOIs
StatePublished - Nov 1 2014

Keywords

  • Graph coloring
  • K-critical graphs
  • Sparse graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Ore's conjecture on color-critical graphs is almost true'. Together they form a unique fingerprint.

  • Cite this