A linear bound on some size Ramsey numbers for cycles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
The size Ramsey number \( \hat{r}(G,H)\) is the least integer \( m\) for which there exists a graph \( F\) with \( m\) edges so that in any coloring of the edges of \( F\) in red and blue, there is always either a red copy of \( G\) or a blue copy of \( H\). Sometimes we write \( F \rightarrow (G,H)\) to denote this. For \( G=H\), we denote \( \hat{r}(G,G)\) by \( \hat{r}(G)\).
In [1], Erdös, Faudree, Rousseau and Schelp raised the following problem:
Problem
Is it true that \[ r(C_m, H) \leq 2n+ \lceil (m1)/2 \rceil \] where \(m \geq 3\) and \(H\) is a graph consisting of \(n\) edges without isolated vertices?
Bibliography  

1 
P. Erdös, R. Faudree, C. C. Rousseau and R. H. Schelp,
Ramsey size linear graphs, Combin. Probab.
Comput. 2 (1993), 389399.
