The size-Ramsey number of powers of paths
View / Open Files
Publication Date
2019Journal Title
Journal of Graph Theory
ISSN
0364-9024
Publisher
Wiley
Volume
91
Issue
3
Pages
290-299
Type
Article
This Version
AM
Metadata
Show full item recordCitation
Clemens, D., Jenssen, M., Kohayakawa, Y., Morrison, N., Mota, G., Reding, D., & Roberts, B. (2019). The size-Ramsey number of powers of paths. Journal of Graph Theory, 91 (3), 290-299. https://doi.org/10.1002/jgt.22432
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.
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).
Identifiers
External DOI: https://doi.org/10.1002/jgt.22432
This record's URL: https://www.repository.cam.ac.uk/handle/1810/287368
Rights
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk