The Multicolor Size-Ramsey Number of Bipartite Long Subdivisions

Abstract

For a positive integer $r$, the $r$-color size-Ramsey number~${\hat{R}}_r(H)$ of a graph $H$ is the minimum number of edges in a graph $G$ such that every $r$-edge coloring of $G$ contains a monochromatic copy of $H$. For a graph~$H$ and a function $\sigma :E(H)\to \mathbb{N}$, the \emph{subdivision} $H^{\sigma }$ is obtained by replacing every $e\in E(H)$ with a path of length $\sigma (e)$. In~\cite{javadi25:_induced_long} it is shown that for all integers $r,D\ge 2$, there exists a constant $c=c(r,D)$ such that for every graph $H$ with maximum degree $D$ if $H^{\sigma }$ is a subdivision of~$H$ in which $\sigma (e)>c\log n$ for every $e\in E(H)$, where $n=|V(H^{\sigma })|$, then ${\hat{R}}_r(H^{\sigma })=O(2^{34r}{r}^6{\log }^5(r)D^5\log D)n.$ We improve upon this result in the case that~$H^{\sigma }$ is a bipartite graph and the number of colors~$r$ is large using a significantly different argument, obtaining the bound ${\hat{R}}_r(H^{\sigma })\le r^{400D\log D}n$.