Advanced Search

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

Cited in: Zbl 1242.05174 Zbl 1227.05194 Zbl 1049.05055 Zbl 1048.05063 Zbl 0988.05064 Zbl 0963.05094 Zbl 0931.05057

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]