##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 284.05106

**Autor: ** Andrasfai, B.; Erdös, Paul; Sos, V.T.

**Title: ** On the connection between chromatic number, maximal clique and minimal degree of a graph. (In English)

**Source: ** Discrete Math. 8, 205-218 (1974).

**Review: ** 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.

**Reviewer: ** J.Mitchem

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag