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 (m-1)/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), 389-399.
|