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 language||English (US)|
|Number of pages||10|
|State||Published - 2000|
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics