Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0248.05127
Bondy, J.A.; Erd\H{o}s, Paul
Ramsey numbers for cycles in graphs.
(English)
[J] J. Comb. Theory, Ser. B 14, 46-54 (1973). ISSN 0095-8956

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 {\it J. Faudree} and {\it R. H. Schelp} [Discrete Math. 8, 313-329 (1974; Zbl 0294.05122)] and {\it 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) \le nr^2$ for all $r$ and $n$ and that $(R(C_n,K_r)=(r-1)(n-1)+1$ if $n \ge 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$.

Display scanned Zentralblatt-MATH page with this review.
[G.Chartrand]
MSC 2000:
*05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps

Citations: Zbl 0294.05122; Zbl 0261.05118; Zbl 0261.05119

Highlights
Master Server