Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 333.05120
Autor: Burr, Stefan A.; Erdös, Paul; Lovász, László
Title: On graphs of Ramsey type. (In English)
Source: Ars combinat. 1, 167-190 (1976).
Review: Let F be a graph and G and H sets of graphs. (All graphs will be finite and simple.) A colouring of F will be a sequence of subgraphs of H – each having the same vertex-set as F – such that their edge-sets form a disjoint partition of the edge-set of F. F ––> (G,H) means that in any 2-colouring of F either the first part contains a subgraph isomorphic to a member of G, or the second part contains a subgraph isomorphic to a member of H. When G = H, the notation is simplified to F ––> G. When G or H contain but a single graph, the notation is adjusted so that the name of the unique member replaces the name of the set. For any graph G, \kappa (G) denotes the connectivity of G; for any positive integer m, mG denotes the disjoint union of m copies of G. The set of homomorphic images of G is denoted by \hom G. The direct product G × H of two graphs G and H is the graph with vertex-set V(G) × V(H), otherwise known as the conjunction. The chromatic Ramsey number rc(G,H) is the least integer m for which there exists a graph F such that F ––> (G,H) and \chi (F) = m; the Ramsey number r(G,H) is the least integer n such that Kr ––> (G,H). Theorem 1: For any classes G and H, rc(G,H) = r(\hom G, \hom H). Theorem 2: Let G and H be graphs of chromatic number r, and suppose that every vertex of H is contained in a complete (r-1)-graph. Then G × H has chromatic number r. Two conjectures are stated: Conjecture 1: max rc(G) = (r-1)2+1, where the minimum is taken over all r-chromatic graphs. Conjecture 2: \chi (G × H) = max (\chi (G), \chi (H)). (A weakened version of Conjecture 2 follows from Theorem 2. The truth of Conjecture 2 would imply that of Conjecture 1.) Theorem 3: Conjecture 1 is valid for r = 4. Define \delta (F) and \Delta (F) to be the minimum and maximum degrees of vertices of F. F is (G,H)-irreducible if F ––> (G,H) but no proper subgraph of F has this property. Theorem 4: 2r/2 \leq max \Delta (G) \leq r(Kr)-1, where the minimum is taken over all G for which G ––> Kr. Theorem 5: max \delta (G) = (r-1)(s-1), where the minimum is taken over all (Kr,Ks)-irreducible graphs. Theorem 6: If r,s \geq 3, there are infinitely many non-isomorphic (Kr,Ks)-irreducible graphs. Theorem 7: If r,s \geq 3, then there exists (Kr,Ks)-irreducible graphs with arbitrarily large \Delta. Theorem 8: If r,s \geq 3, then max K(G) = 2 or 3 according as r \ne s or r = s, where the minimum is taken over all (Kr,Ks)-irreducible graphs G. Theorem 9: A necessary and sufficient condition that G ––> K1,n is that \Delta (G) \geq 2n-1, or, if n is even, that G has a component which is regular of degree 2n-2 and which has an odd number of vertices. Theorem 10: G ––> 2K2 if and only if G contains three disjoint edges or a 5-cycle. Theorem 11: For any positive integers m and n, the number of (mK2,nK2)-irreducible graphs is finite.
Reviewer: W.G.Brown
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag