On the number of edges in colour-critical graphs and hypergraphs

A. V. Kostochka, M. Stiebitz

Research output: Contribution to journalArticlepeer-review

Abstract

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/3√k)n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.

Original languageEnglish (US)
Pages (from-to)521-530
Number of pages10
JournalCombinatorica
Volume20
Issue number4
DOIs
StatePublished - 2000

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'On the number of edges in colour-critical graphs and hypergraphs'. Together they form a unique fingerprint.

Cite this