×

An improved bound on the minimal number of edges in color-critical graphs. (English) Zbl 0885.05063

Electron. J. Comb. 5, Research paper R4, 4 p. (1998); printed version J. Comb. 5, 61-64 (1998).
Summary: It is proven that for \(k\geq 4\) and \(n>k\) every \(k\)-color-critical graph on \(n\) vertices has at least \(\left(\frac{k-1}{2}+\frac{k-3}{2(k^2-2k-1)}\right)n\) edges, thus improving a result of Gallai from 1963.

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS