The size‐Ramsey number of powers of paths
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Abstract
Abstract Given graphs and and a positive integer , say that is ‐ Ramsey for , denoted , if every ‐coloring of the edges of contains a monochromatic copy of . The size‐Ramsey number of a graph is defined to be . Answering a question of Conlon, we prove that, for every fixed , we have , where is the th power of the ‐vertex path (ie, the graph with vertex set and all edges such that the distance between and in is at most ). Our proof is probabilistic, but can also be made constructive.
Description
Journal Title
Journal of Graph Theory
Conference Name
Journal ISSN
0364-9024
1097-0118
1097-0118
Volume Title
91
Publisher
Wiley
Publisher DOI
Rights and licensing
Except where otherwised noted, this item's license is described as http://www.rioxx.net/licenses/all-rights-reserved
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).