Degree Ramsey Numbers of Closed Blowups of Trees

  • Paul Horn University of Denver
  • Kevin G. Milans West Virginia University
  • Vojtěch Rödl Emory University
Keywords: Ramsey Theory, Graph Theory

Abstract

The degree Ramsey number of a graph $G$, denoted $R_\Delta(G;s)$, is $\min\{\Delta(H)\colon\, H\stackrel{s}{\to} G\}$, where $H\stackrel{s}{\to} G$ means that every $s$-edge-coloring of $H$ contains a monochromatic copy of $G$.  The closed $k$-blowup of a graph is obtained by replacing every vertex with a clique of size $k$ and every edge with a complete bipartite graph where both partite sets have size $k$.  We prove that there is a function $f$ such that $R_\Delta(G;s) \le f(\Delta(G), s)$  when $G$ is a closed blowup of a tree.

Published
2014-04-16
Article Number
P2.5