dc.contributor.author Clemens, D dc.contributor.author Jenssen, M dc.contributor.author Kohayakawa, Y dc.contributor.author Morrison, N dc.contributor.author Mota, GO dc.contributor.author Reding, D dc.contributor.author Roberts, B dc.date.accessioned 2018-12-22T00:30:29Z dc.date.available 2018-12-22T00:30:29Z dc.date.issued 2019 dc.identifier.issn 0364-9024 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/287368 dc.description.abstract Given graphs $G$ and $H$ and a positive integer $q$, say that $G$ \emph{is $q$-Ramsey for} $H$, denoted $G\rightarrow (H)_q$, if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The \emph{size-Ramsey number} $\sr(H)$ of a graph $H$ is defined to be $\sr(H)=\min\{|E(G)|\colon G\rightarrow (H)_2\}$. Answering a question of Conlon, we prove that, for every fixed~$k$, we have $\sr(P_n^k)=O(n)$, where~$P_n^k$ is the $k$th power of the $n$-vertex path $P_n$ (i.e., the graph with vertex set $V(P_n)$ and all edges $\{u,v\}$ such that the distance between $u$ and $v$ in $P_n$ is at most $k$). Our proof is probabilistic, but can also be made constructive. dc.description.sponsorship Most of the work for this paper was done during my PhD, which was half funded by EPSRC grant reference 1360036, and half by Merton College Oxford. The third author was partially supported by FAPESP (Proc.~2013/03447-6) and by CNPq (Proc.~459335/2014-6, 310974/2013-5). The fifth author was supported by FAPESP (Proc.~2013/11431-2, Proc.~2013/03447-6 and Proc.~2018/04876-1) and partially by CNPq (Proc.~459335/2014-6). This research was supported in part by CAPES (Finance Code 001). The collaboration of part of the authors was supported by a CAPES/DAAD PROBRAL grant (Proc.~430/15). dc.publisher Wiley dc.subject powers of paths dc.subject Ramsey dc.subject size-Ramsey dc.title The size-Ramsey number of powers of paths dc.type Article prism.endingPage 299 prism.issueIdentifier 3 prism.publicationDate 2019 prism.publicationName Journal of Graph Theory prism.startingPage 290 prism.volume 91 dc.identifier.doi 10.17863/CAM.34672 dcterms.dateAccepted 2018-08-18 rioxxterms.versionofrecord 10.1002/jgt.22432 rioxxterms.version AM rioxxterms.licenseref.uri http://www.rioxx.net/licenses/all-rights-reserved rioxxterms.licenseref.startdate 2019-07-01 dc.contributor.orcid Kohayakawa, Y [0000-0001-7841-157X] dc.contributor.orcid Mota, GO [0000-0001-9722-1819] dc.identifier.eissn 1097-0118 rioxxterms.type Journal Article/Review cam.issuedOnline 2018-12-02 rioxxterms.freetoread.startdate 2019-12-02
﻿