\(K_ 5\) is the only double-critical 5-chromatic graph
A connected graph G is called double-critical if the chromatic number of G decreases by 2 when any two adjacent vertices of G are deleted. \textit{L. Lovász} [Theory of Graphs, Proc. Colloquium Tihany, Hungary 1966, 231- 236 (1968; Zbl 0157.312)] conjectured that \(K_ n\), the complete graph of order n, is the only double-critical graph having chromatic number n. This conjecture can be easily verified for \(n\leq 4\). The present author gives a nice, short proof of this conjecture for the case \(n=5\).
scientific article; zbMATH DE number 3991528