## On the magnitude of generalized Ramsey numbers for graphs.(English)Zbl 0316.05110

Infinite finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 215-240 (1975).
[For the entire collection see Zbl 0293.00009.]
Let $$G$$ and $$H$$ be graphs and let $$r(G,H)$$ be the least number so that any edge 2-coloring of $$K_p$$ (the complete graph on $$p$$ vertices) with $$p \geq r(G,H)$$ contains either a subgraph isomorphic with $$G$$ all of whose edges are colored with the first color or a subgraph isomorphic with $$H$$ all of whose edges are colored with the second color. We let $$r(G)$$ denote $$r(G,G)$$. This paper is devoted to a study of the asymptotic properties of the functions $$r(G,H)$$ and $$r(G)$$. Central to this discussion is the concept of an $$L$$-set: A set $$\{G_1,G_2, \ldots \}$$ of graphs is called an $$L$$-set if there is a constant $$c$$ so that $$r(G_i) \leq c \cdot p(G_i)$$, for all $$i$$, where $$p(G_i)$$ denotes the number of vertices of $$G_i$$. Also a set of ordered pairs $$\{(G_1,H_1),(G_2,H_2), \ldots \}$$ of graphs is called an $$L$$-set if there is a constant $$c$$ so that $$r(G_i,H_i) \leq c \cdot (p(G_i)+p(H_i))$$, for all $$i$$. Many special cases of, and results related to, the following conjecture are proved in this paper. Conjecture: Any set of graphs or pairs of graphs having bounded arboricity is an $$L$$-set. For example Theorem 3.1. Suppose $$\{G_1,G_2, \ldots \}$$ is an $$L$$-set having bounded arboricity. Then $$\{G_1+K_1,G_2+K_1, \ldots \}$$ is an $$L$$-set. Theorem 3.5. If $$n \geq r(K_k)$$, $$k \geq 2$$ and $$G$$ denotes the graph $$K_k \cup (n-k)K_1$$, then for some absolute constant $$c$$, $$k_n+1 \leq r(G+K_1) \leq kn+cn/k$$. Theorem 4.1. There exist graphs $$\{G_1,G_2, \ldots \}$$ and $$\{H_1,H_2, \ldots \}$$ such that $$\{(G_1,H_1)(G_2,H_2), \ldots \}$$ is an $$L$$-set but $$\{G_1,G_2, \ldots \}$$ and $$\{H_1,H_2, \ldots \}$$ are no $$L$$-sets.
Reviewer: J.E.Graver

### MSC:

 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory

Zbl 0293.00009