\documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.5}{21(2)}{2014} \usepackage{amsmath,amsthm,amssymb} %,mathrsfs} %\usepackage[T1]{fontenc} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Degree Ramsey numbers of\\ closed blowups of trees} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Paul Horn\\ \small Department of Mathematics\\[-0.8ex] \small University of Denver\\[-0.8ex] \small Denver, CO, U.S.A.\\ \small\tt paul.horn@du.edu\\ \and Kevin G. Milans\\ \small Department of Mathematics\\[-0.8ex] \small West Virginia University\\[-0.8ex] \small Morgantown, WV, U.S.A.\\ \small\tt milans@math.wvu.edu\\ \and Vojt\v{e}ch R\"{o}dl\thanks{Partially supported by NSF grant DMS0800070.}\\ \small Department of Mathematics and Computer Science\\[-0.8ex] \small Emory University\\[-0.8ex] \small Atlanta, GA, U.S.A.\\ \small\tt rodl@mathcs.emory.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jul 8, 2012}{Apr 3, 2014}{Apr 16, 2014}\\ \small Mathematics Subject Classifications: 05C55, 05D10} \begin{document} \maketitle % \dr for "Degree Ramsey" \newcommand{\dr}{R_{\Delta}} \newcommand{\sarrow}{\stackrel{s}{\to}} \newcommand{\st}{\colon\,} %such that \newcommand{\etal}{et al.\ } \newcommand{\G}{\mathcal{G}} \newcommand{\F}{\mathcal{F}} \newcommand{\ceil}[1]{{\left\lceil #1 \right\rceil}} \begin{abstract} The degree Ramsey number of a graph $G$, denoted \emph{$\dr(G;s)$}, is $\min\{\Delta(H)\st H\sarrow G\}$, where $H\sarrow 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 $\dr(G;s) \le f(\Delta(G), s)$ when $G$ is a closed blowup of a tree. \end{abstract} \section{Introduction} When $G$ is a graph, we use $V(G)$ to denote the vertex set of $G$ and $E(G)$ to denote the edge set. The degree of a vertex $u$ in $G$ is denoted by $d(u)$. Given graphs $H$ and $G$, we write $H\sarrow G$ if every $s$-edge-coloring of $H$ contains a monochromatic copy of $G$. For graphs, Ramsey's Theorem implies that for every graph $G$ and each positive integer $s$, there is a graph $H$ such that $H\sarrow G$. When $H\sarrow G$, we call $G$ the \emph{target graph} and $H$ a \emph{Ramsey host} for $G$. The main goal of graph-based Ramsey theory is to understand the relation $H\sarrow G$. Typically, a target graph $G$ is fixed and one seeks a Ramsey host for $G$ that has a desired property or is extremal with respect to a certain parameter. The \emph{Ramsey number} of a graph $G$, denoted $R(G;s)$, is $\min\{|V(H)|\st H\sarrow G\}$. Chv\'atal, R\"odl, Szemer\'edi, and Trotter~\cite{DR-linear-Ramsey} proved that for each $k$, there is a constant $c_k$ such that $R(G;2)\le c_k|V(G)|$ whenever $G$ has maximum degree at most $k$. In other words, the Ramsey numbers of bounded degree graphs grow only linearly with the number of vertices, in marked contrast to the exponential growth that occurs when the bounded degree condition is omitted. Several groups generalized this result to multicolored hypergraphs (see~\cite{lin-hypA} and \cite{lin-hypC}). The \emph{size Ramsey number} of $G$, denoted $R'(G;s)$, is $\min\{|E(H)|\st H\sarrow G\}$. Beck~\cite{beck1983} proved that for each $s$, there exists a constant $c_s$ such that $R'(P_n;s) \le c_s n$, where $P_n$ is the path on $n$ vertices. Beck asked whether the size Ramsey numbers of bounded degree graphs also grow linearly in the number of vertices. In addition to paths, Beck's question was answered in the affirmative for trees~\cite{DR-sizeRamTrees} and cycles~\cite{DR-Haxell}. However, R\"odl and Szemer\'edi~\cite{RS} resolved Beck's question in the negative by constructing a family of $3$-regular graphs whose size Ramsey numbers grow superlinearly. We consider a variant of Beck's question where we no longer require our Ramsey hosts to have few edges but we do insist they have bounded degree. The \emph{degree Ramsey number}, denoted $R_\Delta(G;s)$, is $\min\{\Delta(H)\st H\sarrow G\}$, where $\Delta(H)$ denotes the maximum degree in $H$. The degree Ramsey analogue of Beck's question follows naturally. \begin{question}\label{q} Is $R_\Delta(G;s)$ bounded by a function of $\Delta(G)$ and $s$? \end{question} A family of graphs $\G$ is \emph{$R_\Delta$-bounded} if there is a function $f(d,s)$ such that $R_\Delta(G;s)\le f(\Delta(G),s)$ for every $G\in\G$. Question~\ref{q} is then whether or not the family of all graphs is $R_\Delta$-bounded. Paths~\cite{alon2003} and cycles~\cite{DR-Haxell,JMW} are $R_\Delta$-bounded. Extending the Alon~\etal argument for paths, Jiang observed that $R_\Delta(T;s)\le 2s(\Delta(T)-1)$ when $T$ is a tree, and this bound is nearly sharp when $s$ and $\Delta(T)$ are large~\cite{KMW}. While we are unable to resolve Question~\ref{q}, we believe that the family of all graphs is not $R_\Delta$-bounded. Our work was motivated by a concrete problem in the direction of Question~\ref{q}. For a graph $G$, let $G^k$ denote the graph on $V(G)$ where distinct vertices are adjacent if and only if their distance in $G$ is at most $k$. Is the family of powers of paths $\dr$-bounded? Even the special case of determining whether $\dr(P_n^2; s)$ is bounded by a function of $s$ is not clear. In this note, we resolve this problem. In fact, we prove more. The \emph{closed $k$-blowup} of $G$, denoted $G[k]$, is the graph obtained from $G$ by replacing each vertex in $G$ with a clique of size $k$ and each edge in $G$ with a complete bipartite graph whose partite sets each have size $k$. We show that the family of closed blowups of trees is $R_\Delta$-bounded. It follows that the family of powers of paths is $\dr$-bounded since $P_n^k$ is a subgraph of $P_\ceil{n/k}[k]$ and $\Delta(P_\ceil{n/k}[k]) < \frac{3}{2}\Delta(P_n^k)$ when $n$ is large in terms of $k$. One interesting test case for Question~\ref{q} is the family of grids $P_n~\Box~P_n$, where $G~\Box~H$ is the graph on $V(G)\times V(H)$ with $(u_1,v_1)(u_2,v_2)\in E(G~\Box~H)$ if and only if $u_1=u_2$ and $v_1v_2\in E(H)$ or $v_1=v_2$ and $u_1u_2\in E(G)$. It is not known whether the family of grids is $R_\Delta$-bounded. In addition to minimizing $|V(H)|$, $|E(H)|$, and $\Delta(H)$, several researchers have sought Ramsey hosts $H$ that are extremal with respect chromatic number~\cite{BEL} and clique number~\cite{folkman1970,NR,nr-simp}. The former reference also provides exact results on the degree Ramsey numbers of complete graphs and stars; in particular, $R_\Delta(K_n;s) = R(K_n;s)-1$. \section{Construction} A graph is $d$-regular if every vertex has degree $d$, and the \emph{girth} of a graph is the minimum number of vertices in a cycle. Erd\H{o}s and Sachs~\cite{ErdosSachs} proved that for every $d$ and $g$, there is a $d$-regular graph with girth $g$. Alon, Ding, Oporowski, and Vertigan~\cite{alon2003} observed that if $H$ has girth at least $n$ and average degree at least $2s$, then $H\sarrow P_n$, where $P_n$ is the path on $n$ vertices. Jiang~\cite{JMW} noted that their argument extends to the case that the target graph is a tree. We include the short proof for completeness. \begin{lemma}\label{lem:dr-tree} If $T$ is a tree with $|V(T)| \ge 3$ and $H$ is a graph with average degree at least $2s(\Delta(T)-1)$ and girth at least $|V(T)|$, then $H\sarrow T$. \end{lemma} \begin{proof} Consider an $s$-edge-coloring of $H$ and let $n=|V(H)|$. Since $H$ has average degree at least $2s(\Delta(T)-1)$, we have $|E(H)| \ge ns(\Delta(T)-1)$ and hence some color is used on at least $n(\Delta(T)-1)$ edges. Let $H_0$ be a monochromatic subgraph of $H$ with at least $ns(\Delta(T)-1)$ edges. It follows that $H_0$ contains a subgraph $H_1$ with $\delta(H_1) \ge \Delta(T)$. Indeed, if every subgraph of $H_0$ had a vertex $u$ with $d(u) \le \Delta(T)-1$, then iteratively deleting vertices of minimum degree would yield $|E(H_0)| \le (n-1)(\Delta(T)-1) < n(\Delta(T)-1)$, a contradiction. Let $H_1$ be a subgraph of $H_0$ with $\delta(H_1) \ge \Delta(T)$. Since $H_1$ has minimum degree at least $\Delta(T)$ and girth at least $|V(T)|$, a well known greedy embedding strategy finds $T$ as a subgraph of $H_1$. Hence $H\sarrow T$. \end{proof} Hence, for each tree $T$ with at least $3$ vertices, Lemma~\ref{lem:dr-tree} implies that $\dr(T;s)\le 2s(\Delta(T)-1)$. Our main theorem generalizes this bound to the case where the target graph is a closed blowup of a tree. Let $[n] = \{1,\ldots,n\}$, and, when $S$ is a set, let $\binom{S}{k}$ be the set of subsets of $S$ of size $k$. We will need the well known strengthening of the Erd\H{o}s and Sachs result that for every $d$ and $g$, there is a bipartite $d$-regular graph with girth at least $g$. \newcommand{\wht}{{t'}} \newcommand{\Bst}{B^{\star}} \newcommand{\est}{e^{\star}} \begin{theorem}~\label{thm:dr} Let $k$ and $s$ be integers with $k\ge 2$ and $s\ge 1$, and let $r=R(K_{2k};s)$. If $T$ is a tree with $|V(T)| \ge 3$, then $\dr(T[k];s) \le (r-1)\left(2\binom{r}{2k}(\Delta(T)-1)\right)^{\binom{r-1}{2k-1}}$. \end{theorem} \begin{proof} Let $t=\binom{r}{2k}$, $\wht =\binom{r-1}{2k-1}$, $d=2t(\Delta(T)-1)$, and let $B$ be a $d$-regular $(X,Y)$-bigraph with girth at least $|V(T)|$. To construct a Ramsey host for $T[k]$, we first use $B$ to construct an $r$-uniform, $r$-partite hypergraph $F$. The partite sets of $F$ are $Z_1, \ldots, Z_r$. The vertices in $Z_j$ are certain $t$-tuples of elements in $V(B)\cup E(B)$, indexed by $\binom{[r]}{2k}$. When $w$ is such a tuple and $A\in\binom{[r]}{2k}$, we use $w_A$ to denote the $A$-value of $w$. For each $A\in \binom{[r]}{2k}$, let $A^-$ be the $k$ smallest integers in $A$ and $A^+$ be the $k$ largest integers in $A$. The partite set $Z_j$ consists of all tuples $w$ such that for each coordinate $A$, the $A$-value of $w$ belongs to $X$, $Y$, or $E(B)$ according to whether $j\in A^-$, $j\in A^+$, or $j\not\in A$, respectively. It remains to specify the edges of $F$. In the following, we use $w_{j,A}$ to denote the $A$-value of a vertex $w_j \in Z_j$. When $u\in X$, $v\in Y$, and $uv\in E(B)$, we say that the edge $uv$ \emph{satisfies the $A$-coordinate} of $w_j \in Z_j$ if \[ w_{j,A} = \begin{cases} u & \mbox{if $j\in A^-$}\\ v & \mbox{if $j\in A^+$}\\ uv & \mbox{if $j\not\in A$}. \end{cases} \] Consider $w_1,\ldots, w_r$ with $w_j\in Z_j$ for each $j$. We let $w_1\ldots w_r\in E(F)$ if and only if for each coordinate $A \in \binom{[r]}{2k}$, there is some edge in $B$ that simultaneously satisfies the $A$-coordinate of each vertex in $\{w_1, \ldots, w_r\}$. We obtain our host graph $H$ from $F$ by replacing each edge in $F$ with an $r$-clique in $H$. Consequently, $w_i\in Z_i$ and $w_j \in Z_j$ are adjacent in $H$ if and only if for each $A\in \binom{[r]}{2k}$, there is an edge in $B$ that satisfies the $A$-coordinates of $w_i$ and $w_j$. To motivate our construction, we note that $H$ contains many copies of $B[k]$, the closed $k$-blowup of $B$. For each coordinate $A\in\binom{[r]}{2k}$ and each function $h\st \binom{[r]}{2k} - \{A\} \to E(B)$, we obtain a copy of $B[k]$ in $H$. The copy of $B[k]$ in $H$ is specified by the function $g_{A,h}\st V(B)\to \binom{V(H)}{k}$, defined as follows: \begin{align*} g_{A,h}(u) = \{w\st &\mbox{$w_A = u$ and} \\ & \mbox{$\forall A'\in \binom{[r]}{2k}$ if $A'\ne A$, then $h(A')$ satisfies the $A'$-coordinate of $w$}\}. \end{align*} Note that at most one vertex in each partite set is a candidate for inclusion in $g_{A,h}(u)$. Moreover, the condition $w_A = u$ requires that $u\in X$ and $j\in A^-$ or that $u\in Y$ and $j\in A^+$. Since $|A^-| = |A^+| = k$, always $|g_{A,h}(u)| = k$. Finally, if $uv\in E(B)$ with $u\in X$ and $v\in Y$, it follows from the definition of $F$ that $g_{A,h}(u) \cup g_{A,h}(v)$ is contained in the edge in $F$ where $uv$ satisfies the $A$-coordinate and the other coordinates are satisfied by the corresponding images of $h$. Let $m = |E(B)|$. Since each edge in $F$ is determined by selecting for each $A\in \binom{[r]}{2k}$ an edge in $B$ to satisfy the $A$-coordinate, we have that $|E(F)|=m^t$. It remains to show that $\Delta(H) \le (r-1)d^{\wht}$ and that $H\sarrow T[k]$. We claim that $F$ is $d^\wht$-regular. Consider a vertex $w_j\in Z_j$. Indeed, if $w_j$ belongs to an edge $e\in E(F)$, then each coordinate is satisfied by some edge in $B$. If $j\not \in A$, then $w_{j,A}\in E(B)$ and the $A$-value of all other vertices is forced. If $j\in A$ and $w_{j,A} = u$, then the $A$-value of all other vertices is determined by selecting an edge in $B$ to satisfy the $A$-coordinate, which must be incident to $u$. Since $u$ is incident to $d$ edges in $B$ and $\wht$ of the coordinates in $\binom{[r]}{2k}$ contain $j$, the claim follows. Moreover, since $F$ is $r$-uniform, replacing each edge in $F$ with a clique increases the degree at each vertex by at most a factor of $r-1$, and therefore $\Delta(H)\le (r-1)d^\wht$. Finally, we show that $H\sarrow T[k]$. Consider an $s$-edge-coloring of $H$ and let $e$ be an edge in $F$. Since $e$ becomes an $r$-clique in $H$ and $r=R(K_{2k};s)$, there is a monochromatic $2k$-clique contained in $e$. For each $e\in E(F)$, choose $S_e \in \binom{[r]}{2k}$ so that $\{w\in e \st \mbox{$w\in Z_j$ for some $j\in S_e$}\}$ is a monochromatic $2k$-clique in $H$. Hence, there exists a coordinate $A\in \binom{[r]}{2k}$ such that at least $m^t/t$ edges $e\in E(F)$ have $S_e = A$; in the following, fix such a coordinate $A$. The \emph{signature} of an edge $e\in E(F)$ with $S_e = A$ is the function $h\st \binom{[r]}{2k}-A \to E(B)$ that records, for every other coordinate $A'$ besides $A$, the edge in $B$ that satisfies $A'$. Since there are $m^{t - 1}$ signatures, some signature is common to at least $\frac{m^t}{t} \cdot \frac{1}{m^{t-1}}$ edges in $F$. Fix such a signature $h$. Let $F'$ be the subhypergraph of $F$ consisting of all edges $e\in E(F)$ such that $S_e = A$ and the signature of $e$ is $h$. Note that $F'$ has at least $m/t$ edges. We use $F'$ to obtain a subgraph $\Bst$ of $B$. For each edge $e$ in $F'$, let $\est$ be the edge in $B$ that satisfies the $A$-coordinate. Note that the map $e\mapsto \est$ is injective since the signature of each edge in $F'$ is $h$. Let $\Bst$ be the subgraph of $B$ with edge set $\{\est\st e\in E(F')\}$. We associate each vertex $u$ in $B$ with the $k$-clique $g_{A,h}(u)$ in $H$. Note that each edge in $\Bst$ corresponds to a monochromatic $2k$-clique in $H$. Since $B$ is $d$-regular with $m$ edges and $\Bst$ has at least $m/t$ edges, it follows that the average degree of $\Bst$ is at least $d/t$. Since $d/t = 2(\Delta(T)-1)$, an application of Lemma~\ref{lem:dr-tree} with $s=1$ implies that $T$ is a subgraph of $\Bst$. The copy of $T$ in $\Bst$ maps via $g_{A,h}$ to a copy of $T[k]$ in $H$ in which each $2k$-clique corresponding to an edge in $T$ is monochromatic. Since $k\ge2$ and $T$ is connected, it follows that the copy of $T[k]$ is monochromatic. \end{proof} We make no attempt to optimize the bound in Theorem~\ref{thm:dr}. Note that the argument of Theorem~\ref{thm:dr} also applies in the hypergraph setting. The complete $q$-uniform $n$-vertex hypergraph is denoted by $K_n^{(q)}$. Let $k$ and $q$ be integers with $k\ge q$, let $s$ be a positive integer, and let $r=R(K^{(q)}_{2k};s)$. Let $G$ be the $q$-uniform $k$-blowup of a tree $T$ on at least $3$ vertices obtained by replacing each vertex $u$ in $T$ with a set $S_u$ of $k$ vertices and replacing each edge $uv$ in $T$ with a copy of $K_{2k}^{(q)}$ on $S_u \cup S_v$. Repeating the construction above (except that each edge of $F$ is replaced with a copy of $K_r^{(q)}$) yields a $q$-uniform hypergraph $H$ with $H\sarrow G$ and $\Delta(H)\le \binom{r-1}{q-1}\left(2\binom{r}{2k}(\Delta(T)-1)\right)^{\binom{r-1}{2k-1}}$. Theorem~\ref{thm:dr} constructs a Ramsey host for the closed $k$-blowup of a tree $T$ using a Ramsey host for $T$. It is natural to ask whether such a construction is possible in general. Is it true that the family of closed blowups of $\F$ is $R_\Delta$-bounded whenever $\F$ is $R_\Delta$-bounded? The analogous statement for \emph{open blowups}, where vertices are replaced with independent sets and edges are replaced with complete bipartite graphs, holds~\cite{JMW}. It is also of interest to find larger $R_\Delta$-bounded graph families. For example, is the family of planar graphs $R_\Delta$-bounded? Since the grids $P_n~\Box~P_n$ are planar, this question seems challenging. However, Theorem~\ref{thm:dr} implies that the family of outerplanar graphs is $R_\Delta$-bounded. Indeed, if $G$ is a $2$-connected outerplanar graph with maximum degree $d$, then for every edge $uv$ on the outer cycle of $G$, we have that $G$ is a subgraph of a closed $(2d)$-blowup of a rooted tree $T$ in which each vertex has at most $2d-3$ children and the root of $T$ expands to contain the image of $u$, $v$, and their neighbors. This is proved by induction on $|V(G)|$; the neighbors of $u$ and $v$ divide $G - u - v$ into at most $2d-3$ pieces which may be treated inductively. The claim then follows from the fact that every outerplanar graph with maximum degree $d$ is a subgraph of a $2$-connected outerplanar graph with maximum degree at most $d+2$. \bibliographystyle{abbrv} \begin{thebibliography}{10} \bibitem{alon2003} N.~Alon, G.~Ding, B.~Oporowski, and D.~Vertigan. \newblock {Partitioning into graphs with only small components}. \newblock {\em Journal of Combinatorial Theory, Series B}, 87(2):231--243, 2003. \bibitem{beck1983} J.~Beck. \newblock {On size Ramsey number of paths, trees, and circuits I}. \newblock {\em J. Graph Theory}, 7(1):115--129, 1983. \bibitem{BEL} S.~Burr, P.~Erd\H{o}s, and L.~Lov\'asz. \newblock {On graphs of Ramsey type}. \newblock {\em Ars Combinatoria}, 1(1):167--190, 1976. \bibitem{DR-linear-Ramsey} C.~Chv{\'a}tal, V.~R{\"o}dl, E.~Szemer{\'e}di, and W.~Trotter, Jr. \newblock The {R}amsey number of a graph with bounded maximum degree. \newblock {\em J. Combin. Theory Ser. B}, 34(3):239--243, 1983. \bibitem{lin-hypA} D.~Conlon, J.~Fox, and B.~Sudakov. \newblock Ramsey numbers of sparse hypergraphs. \newblock {\em Random Structures \& Algorithms}, 35(1):1--14, 2009. \bibitem{lin-hypC} O.~Cooley, N.~Fountoulakis, D.~K{\"u}hn, and D.~Osthus. \newblock Embeddings and ramsey numbers of sparse $\kappa$-uniform hypergraphs. \newblock {\em Combinatorica}, 29(3):263--297, 2009. \bibitem{ErdosSachs} P.~Erd{\H{o}}s and H.~Sachs. \newblock Regul\"are {G}raphen gegebener {T}aillenweite mit minimaler {K}notenzahl. \newblock {\em Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe}, 12:251--257, 1963. \bibitem{folkman1970} J.~Folkman. \newblock {Graphs with monochromatic complete subgraphs in every edge coloring}. \newblock {\em SIAM Journal on Applied Mathematics}, 18(1):19--24, 1970. \bibitem{DR-sizeRamTrees} J.~Friedman and N.~Pippenger. \newblock Expanding graphs contain all small trees. \newblock {\em Combinatorica}, 7(1):71--76, 1987. \bibitem{DR-Haxell} P.~Haxell, Y.~Kohayakawa, and T.~{\L}uczak. \newblock The induced size-{R}amsey number of cycles. \newblock {\em Combin. Probab. Comput.}, 4(3):217--239, 1995. \bibitem{JMW} T.~Jiang, K.~Milans, and D.~West. \newblock {Degree Ramsey numbers of cycles}. \newblock In preparation. \bibitem{KMW} B.~Kinnersley, K.~Milans, and D.~West. \newblock {Degree Ramsey numbers of graphs}. \newblock {\em Combin. Probab. and Comput.} \newblock To appear in the Richard Schelp memorial edition. \bibitem{NR} J.~Ne{\v{s}}et{\v{r}}il and V.~R\"odl. \newblock {Type theory of partition properties of graphs}. \newblock In {\em Recent advances in graph theory}, Proc. Second Czechoslovak Sympos (Prague 1974), pages 405--412, 1975. \bibitem{nr-simp} J.~Ne\v{s}et\v{r}il and V.~R\"{o}dl. \newblock Simple proof of the existence of restricted ramsey graphs by means of a partite construction. \newblock {\em Combinatorica}, pages 199--202, 1981. \bibitem{RS} V.~R\"odl and E.~Szemer\'edi. \newblock {On size Ramsey numbers of graphs with bounded degree}. \newblock {\em Combinatorica}, 20(2):257--262, 2000. \end{thebibliography} \end{document}