Properties of Critical Graphs

In this chapterwe shall continue the study of critical graphs.Critical graphswere first introduced and investigated by G. A. Dirac in his doctoral thesis; he established the basic properties of critical graphs and published the results in the 1950s in a series of papers. The study of critical graphs was continued in the 1960s by G. Hajós, O. Ore, T. Gallai and others. It was believed (G. A. Dirac, private communication to the third author) that the investigation of structural properties of critical graphsmight be of help in proving the four color theorem. However this was too optimistic. Unless P = NP, there is no good characterization of critical graphs with given chromatic number 𝜒 ≥ 4. .