ON THE MINIMAL NUMBER OF EDGES IN COLOR-CRITICAL GRAPHS

A graph G is k-critical if it has chromatic number k, but every proper subgraph of it is (k-1)-colorable. This paper is devoted to investiga ting the following question: for given Ic and n,, what is the minimal number of edges in a k-critical graph on n vertices, with possibly som e additional restrictions imposed? Our main result is that for every k greater than or equal to 4 and n > k this number is at least (k-1/2 k-3/2(k(2)-2k-1))n, thus improving a result of Gallai from 1963. We d iscuss also the upper bounds on the minimal number of edges in k-criti cal graphs and provide some constructions of sparse k-critical graphs. A few applications of the results to Ramsey-type problems and problem s about random graphs are described.