×

Ramsey theorems for multiple copies of graphs. (English) Zbl 0273.05111

If \(G\) and \(H\) are graphs, define the “Ramsey number” \(r(G,H)\) to be the least number \(p\) such that if the edges of the complete graph \(K_p\) are colored red and blue (say), either the red graph contains \(G\) as a subgraph or the blue graph contains \(H\). Let \(mG\) denote the union of \(m\) disjoint copies of \(G\). The following result is proved: Let \(G\) and \(H\) have \(k\) and \(l\) points respectively and have point independence numbers of \(i\) and \(j\) respectively. Then \(N-1 \leq r(mG,nH) \leq N+C\), where \(N=km+ln- \min (mi,nj)\) and where \(C\) is an effectively computable function of \(G\) and \(H\). The method used permits exact evaluation of \(r(mG,nH)\) for various choices of \(G\) and \(H\), especially when \(m=n\) or \(G=H\). In particular, \(r(mK_3,nK_3)=3m+2n\) when \(m \geq n\), \(m \geq 2\).

MSC:

05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI

References:

[1] Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs, Bull. Amer. Math. Soc. 78 (1972), 423 – 426. · Zbl 0234.05117
[2] Stefan A. Burr, Generalized Ramsey theory for graphs — a survey, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973) Springer, Berlin, 1974, pp. 52 – 75. Lecture Notes in Mat., Vol. 406.
[3] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. · Zbl 0182.57702
[4] E. J. Cockayne, An application of Ramsey’s theorem, Canad. Math. Bull. 13 (1970), 145 – 146. · Zbl 0195.25703 · doi:10.4153/CMB-1970-032-5
[5] J. W. Moon, Disjoint triangles in chromatic graphs, Math. Mag. 39 (1966), 259 – 261. · Zbl 0144.23203 · doi:10.2307/2689007
[6] Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs. II. Small diagonal numbers, Proc. Amer. Math. Soc. 32 (1972), 389 – 394. · Zbl 0229.05116
[7] S. A. Burr, Diagonal Ramsey numbers for small graphs, J. Graph Theory 7 (1983), no. 1, 57 – 69. · Zbl 0513.05041 · doi:10.1002/jgt.3190070108
[8] Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335 – 345. · Zbl 0227.05115
[9] Stefan A. Burr and John A. Roberts, On Ramsey numbers for linear forests, Discrete Math. 8 (1974), 245 – 250. · Zbl 0275.05103 · doi:10.1016/0012-365X(74)90136-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.