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) Kr 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) Kr 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