Ramsey numbers for cycles in graphs. (English) Zbl 0248.05127

For two graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the minimum \(p\) such that for any graph \(G\) of order \(p\), either \(G_1\) is a subgraph of \(G\) of \(G_2\) is a subgraph of the complement \(\bar G\) of \(G\). The authors determine the Ramsey numbers in the cases where \(G_1\) and \(G_2\) are certain cycles. [These Ramsey numbers have since been established completely by J. Faudree and R. H. Schelp [Discrete Math. 8, 313-329 (1974; Zbl 0294.05122)] and V. Rosta [J. Comb. Theory, Ser. B 15, 94-104, 105-120 (1973; Zbl 0261.05118 and Zbl 0261.05119)]. The authors show that \(R(C_n,K_r) \leq nr^2\) for all \(r\) and \(n\) and that \((R(C_n,K_r)=(r-1)(n-1)+1\) if \(n \geq r^2-2\). Let \(K^{t+1}_r\) denote the complete \((t+1)\)-partite graph \(K(r_1, \ldots ,r_{t+1})\) for which \(r_i=r\) for each \(i\). Then \(R(C_n,K^{t+1}_r)=t(n-1)+r\) for sufficiently large \(n\).
Reviewer: G.Chartrand


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


[1] Bondy, J. A., Large cycles in graphs, Discrete Mathematics, 1, 121-132 (1971) · Zbl 0224.05120
[2] Chartrand, G.; Schuster, S., On the existence of specified cycles in complementary graphs, Bull. Amer. Math. Soc., 77, 995-998 (1971) · Zbl 0224.05121
[3] Chvátal, V.; Harary, F., Generalized Ramsey theory for graphs, II, Small diagonal numbers, (Proc. Amer. Math. Soc., 32 (1972)), 389-394 · Zbl 0229.05116
[4] Chvátal, V.; Harary, F., Generalized Ramsey theory for graphs, III, Small off-diagonal numbers, Pacific J. Math., 41, 335-345 (1972) · Zbl 0227.05115
[5] Erdös, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 10, 337-356 (1959) · Zbl 0090.39401
[6] Erdös, P.; Stone, A. H., On the structure of linear graphs, Bull. Amer. Math. Soc., 52, 1087-1091 (1946) · Zbl 0063.01277
[7] Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48, 436-452 (1941) · JFM 67.0732.03
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.