Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 333.05119
Autor: Burr, Stefan A.; Erdös, Paul
Title: Extremal Ramsey theory for graphs. (In English)
Source: Utilitas Math. 9, 247-258 (1976).
Review: For graphs G and H the Ramsey number r(G,H) is the least integer p such that in any labelled partition of the complete graph on p vertices into two graphs on the p vertices having disjoint edge sets, either the first contains a copy of G or the second contains a copy of H. The number r(G,G) is denoted by r(G) and called a diagonal Ramsey number. If G and H are sets of graphs, the authors define exr (G) = maxG in Gr(G) and exr(G,H) = maxG in G, H in H r(G,H). Cn,Gn,Kn respectively denote the following classes of graphs: connected on n vertices, n-vertex graphs without isolated vertices, and n-chromatic graphs. Bk,l is the set of connected bipartite graphs with maximal independent sets having k and l vertices. In the theorems of \S2 exr(Cm,Kn) and exr(Gm,Kn) are determined. \S3 is concerned with connected graphs with specified chromatic numbers. In the next section the values of exr(Bk,l) and exr(Bk,l,Bk,l) are determined, also those of exr(Cn) and exr(Cn,Cn). \S5 is concerned with inequalities for exr(Gn) and exr(Gn,Gn). The paper closes with several open problems and conjectures.
Reviewer: W.G.Brown
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag