Brook's theorem (Q2822589)

The paper gives an overview on Brook's theorem, which relates the chromatic number to the maximum degree of a graph.NEWLINENEWLINEAt first, known proofs of the theorem are presented and then developments of the subject are shown. So, critical graphs and bounds of the chromatic number in terms of the clique number and the maximum degree are introduced and explained through known results. Other concepts, such as the list-chromatic number and the equitable chromatic number, arose around the problem of colouring a graph. In this context, this paper is an interesting survey, providing an introduction to the problems that have been studied and to the main unsolved conjectures that arose in these years.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].