## Abstract

A graph G is Ramsey for a graph H if every 2-coloring of the edges of G contains a monochromatic copy of H. We consider the following question: If H has bounded treewidth, is there a sparse graph G that is Ramsey for H? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of H are bounded, then there is a graph G with O(| V (H)| ) edges that is Ramsey for H. This was previously only known for the smaller class of graphs H with bounded bandwidth. On the other hand, we prove that in general the treewidth of a graph G that is Ramsey for H cannot be bounded in terms of the treewidth of H alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and H is a tree.

Original language | English |
---|---|

Pages (from-to) | 281-293 |

Number of pages | 13 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 35 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2021 |

## Keywords

- Bounded treewidth
- Bounded-degree trees
- Ramsey number
- Size ramsey number