On the connection between chromatic number, maximal clique and minimal degree of a graph (Q1844683): Difference between revisions

A well known theorem due to Brooks can be stated as: For \(r \geq 4\), any graph \(G\) has at most 2 of the following properties: (1) \(K_r\) is not contained in \(G\). (2) The chromatic number of \(G\) is at least \(r\). (3) The maximum degree of \(G\) is at most \(r-1\). In this paper the following analogue of Brooks' Theorem is proved via a sequence of lemmas: For \(r \geq 3\), any graph \(G\) with \(n\) vertices has at most two of the following properties: (4) \(K_r\) is not contained in \(G\). (5) The chromatic number of \(G\) is at least \(r\). (6) The minimum degree of \(G\) is greater than \(((3r-7)/(3r-4))n\). The authors also show that if \((3r-4)\) divides \(n\), then there exists a unique graph \(G\) of order \(n\) such that (4) and (5) hold, but the minimum degree of \(G\) is \(((3r-7)/(3r-4))n\).