Projects per year
Abstract
A graph G is Ramsey for a graph H if every 2coloring 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 (fromto)  281293 
Number of pages  13 
Journal  SIAM Journal on Discrete Mathematics 
Volume  35 
Issue number  1 
DOIs  
Publication status  Published  2021 
Keywords
 Bounded treewidth
 Boundeddegree trees
 Ramsey number
 Size ramsey number
Projects
 2 Finished

Enumeration and properties of large discrete structures
Wormald, N. & Liebenau, A.
1/05/18 → 30/08/23
Project: Research

Advances in graph Ramsey theory
Liebenau, A.
Australian Research Council (ARC)
28/06/17 → 28/06/20
Project: Research