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