Color-critical Graphs and Hereditary Hypergraphs

András Sebő

A quick proof of Gallai's celebrated theorem on color-critical graphs is given from Gallai's simple, ingenious lemma on factor-critical graphs, in terms of partitioning the vertex-…