##
**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 r_{c}(__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 K_{r} ––> (__G__,__H__). Theorem 1: For any classes __G__ and __H__, r_{c}(__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** r_{c}(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: 2^{r/2} \leq **max** \Delta (G) \leq r(K_{r})-1, where the minimum is taken over all G for which G ––> K_{r}. Theorem 5: **max** \delta (G) = (r-1)(s-1), where the minimum is taken over all (K_{r},K_{s})-irreducible graphs. Theorem 6: If r,s \geq 3, there are infinitely many non-isomorphic (K_{r},K_{s})-irreducible graphs. Theorem 7: If r,s \geq 3, then there exists (K_{r},K_{s})-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 (K_{r},K_{s})-irreducible graphs G. Theorem 9: A necessary and sufficient condition that G ––> K_{1,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 ––> 2K_{2} 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 (mK_{2},nK_{2})-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