The size-Ramsey number of powers of paths

Authors
Clemens, D 
Jenssen, M 
Morrison, N 

Loading...
Thumbnail Image
Type
Article
Change log
Abstract

Given graphs G and H and a positive integer q, say that G \emph{is q-Ramsey for} H, denoted G→(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)|:G→(H)2}. Answering a question of Conlon, we prove that, for every fixed~k, we have \sr(Pnk)=O(n), where~Pnk is the kth power of the n-vertex path Pn (i.e., the graph with vertex set V(Pn) and all edges {u,v} such that the distance between u and v in Pn is at most k). Our proof is probabilistic, but can also be made constructive.

Publication Date
2019
Online Publication Date
2018-12-02
Acceptance Date
2018-08-18
Keywords
powers of paths, Ramsey, size-Ramsey
Journal Title
Journal of Graph Theory
Journal ISSN
0364-9024
1097-0118
Volume Title
91
Publisher
Wiley
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).