×

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

Citations:

Zbl 0293.00009