Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 316.05110
Autor: Burr, Stefan A.; Erdös, Paul
Title: On the magnitude of generalized Ramsey numbers for graphs. (In English)
Source: Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 215-240 (1975).
Review: [For the entire collection see Zbl 293.00009.]
Let G and H be graphs and let r(G,H) be the least number so that any edge 2-coloring of Kp (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 {G1,G2, ... } of graphs is called an L-set if there is a constant c so that r(Gi) \leq c · p(Gi), for all i, where p(Gi) denotes the number of vertices of Gi. Also a set of ordered pairs {(G1,H1),(G2,H2), ... } of graphs is called an L-set if there is a constant c so that r(Gi,Hi) \leq c · (p(Gi)+p(Hi)), 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 {G1,G2, ... } is an L-set having bounded arboricity. Then {G1+K1,G2+K1, ... } is an L-set. Theorem 3.5. If n \geq r(Kk), k \geq 2 and G denotes the graph Kk \cup (n-k)K1, then for some absolute constant c, kn+1 \leq r(G+K1) \leq kn+cn/k. Theorem 4.1. There exist graphs {G1,G2, ... } and {H1,H2, ... } such that {(G1,H1)(G2,H2), ... } is an L-set but {G1,G2, ... } and {H1,H2, ... } are no L-sets.
Reviewer: J.E.Graver
Classif.: * 05C15 Chromatic theory of graphs and maps
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag