##
**Zentralblatt MATH**

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

**Zbl.No: ** 333.05116

**Autor: ** Bollobás, Béla; Erdös, Paul; Straus, E.G.

**Title: ** Complete subgraphs of chromatic graphs and hypergraphs. (In English)

**Source: ** Utilitas Math. 6, 343-347 (1974).

**Review: ** An r-graph consists of a vertex set V and a set of r-tuples (of vertices). It is k-chromatic if V is partitionable into k color classes such that no r-tuple has two vertices in the same class and k is minimum with this property. The paper considers the case of fixed color classes. A k-chromatic r-graph is called canonical if for every set of r color classes it contains either no or all possible r-tuples (one vertex of each class). It is shown that there is a canonical k-chromatic r-graph having maximum number of r-tuples amongst the k-chromatic r-graphs with given color classes which do not contain a complete r-graph with p vertices. Moreover, in case r = 2 there is a complete (p-1)-partite graph having this maximum property; this is an extension of Turán's famous theorem onto the case of given color classes. Finally it is given a best possible lower bound for the degres of the vertices of a k-chromatic 2-graph G with given color classes to ensure the existence of a triangle in G. The last two results are not generalizable to higher r's.

**Reviewer: ** W.Wessel

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C15 Chromatic theory of graphs and maps

05C99 Graph theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag