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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page