A strengthening of Brooks' theorem (Q1306303): Difference between revisions

This paper mainly proves the conjecture due to \textit{A. Beutelspacher} and \textit{P.-R. Hering} [Ars Comb. 18, 201-216 (1984; Zbl 0554.05025)]. More precisely, the author proves that for sufficiently large \(\Delta\), any graph with maximum degree at most \(\Delta\) and no cliques of size \(\Delta\) has a \(\Delta-1\) colouring. The proof relies on the fact that if \(G\) is a minimal counterexample to the result, then any reasonably dense set of about \(\Delta\) vertices in \(G\) is either a clique or the intersection of two cliques.