Induced Ramsey problems for trees and graphs with bounded treewidth

Abstract

The induced $q$-color size-Ramsey number ${\hat{r}}_{\text{ind}}(H;q)$ of a graph $H$ is the minimal number of edges a host graph $G$ can have so that every $q$-edge-coloring of $G$ contains a monochromatic copy of $H$ which is an induced subgraph of $G$. A natural question, which in the non-induced case has a very long history, asks which families of graphs $H$ have induced Ramsey numbers that are linear in $|H|$. We prove that for every $k,w,q$, if $H$ is an $n$-vertex graph with maximum degree $k$ and treewidth at most $w$, then ${\hat{r}}_{\text{ind}}(H;q)=O_{k,w,q}(n)$. This extends several old and recent results in Ramsey theory. Our proof is quite simple and relies upon a novel reduction argument.

arXiv comment17 pages, comments welcome!