×

A shorter proof of the Dirac theorem on the number of edges in chromatically critical graphs. (Russian) Zbl 0920.05030

All noncomplete \(k\)-critical graphs with minimum \(2| E(G)|- (k-1)| V(G)|\), where \(G\) is the simple finite \(k\)-critical graph, are characterized.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite