An abstract generalization of a map reduction theorem of Birkhoff (Q1907097): Difference between revisions

A graph \(G\) is called \(n\)-contraction-critical, if it has chromatic number \(\chi(G)\geq n\), but \(\chi(G')<n\) holds for every proper minor \(G'\) of \(G\). Hadwiger's conjecture says that there is only one \(n\)-contraction-critical graph, namely \(K_n\). It is well known that every \(n\)-contraction-critical \(G\not\cong K_n\) has minimum degree at least \(n\). The authors study the subgraph \(G^n\) spanned by the vertices of degree \(n\) in an \(n\)-contraction-critical \(G\not\cong K_n\). They show that \(G^n\) does not contain an induced \(K_4^-\), i.e. a \(K_4\) minus an edge. This implies that \(G^n\) is a line graph and by Vizing's theorem that \(G\) has vertices of degree exceeding \(n\), which was proved before by \textit{J. Mayer} [Ann. Discrete Math. 41, 341-345 (1989; Zbl 0692.05034)]. It is now even shown that every \(n\)-contraction-critical \(G\not\cong K_n\) contains at least \(n-4\) vertices of degree exceeding \(n\).