Naslov
The Size Ramsey Number of Graphs with Bounded Treewidth

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

Izvornik
SIAM Journal on Discrete Mathematics (0895-4801) 35 (2021), 1; 281-293

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Ramsey numbers

Sažetak
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(vertical bar V (H)vertical bar) 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA