The size ramsey number of graphs with bounded treewidth

Nina Kamcev, Anita Liebenau, David R. Wood, Liana Yepremyan

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)281-293
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume35
Issue number1
DOIs
Publication statusPublished - 2021

Keywords

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

Cite this