The multicolor induced size-Ramsey number of long subdivisions

Abstract

For a positive integer $k$ and a graph $H$, the $k$-color induced size-Ramsey number ${\hat{R}}_{\mathrm{ind}}(H,k)$ is the minimum integer $m$ for which there exists a graph $G$ with $m$ edges such that for every $k$-edge coloring of $G$, the graph $G$ contains a monochromatic copy of $H$ as an induced subgraph. For a graph $H$ with the edge set $E(H)$ and a function $\sigma :E(H)\to \mathbb{N}$, the subdivision $H^{\sigma }$ is obtained by replacing each $e\in E(H)$ with a path of length $\sigma (e)$. We prove that for all integers $k,D\ge 2$, there exists a constant $c=c(k,D)$ such that the following holds. Let $H$ be any graph with maximum degree $D$ and let $H^{\sigma }$ be a subdivision of $H$ with $\sigma (e)>c{\log }_{D}n$ for every $e\in E(H)$, where $n$ is the order of $H^{\sigma }$. Then, ${\hat{R}}_{\mathrm{ind}}(H^{\sigma },k)=e^{O(k\log k)}{D}^9(\log D)n$. If each $\sigma (e)$ is even and larger than $c{\log }_{D}n$, this bound improves to ${\hat{R}}_{\mathrm{ind}}(H^{\sigma },k)=O(k^{342}(\log k{)}^9{D}^9\log D)n$. We also find improved bounds for the non-induced size-Ramsey number of long subdivisions.

References to the literature revised; 24 pages