TY - JOUR
T1 - The multicolour size-Ramsey number of powers of paths
AU - Han, Jie
AU - Jenssen, Matthew
AU - Yoshiharu Kohayakawa, Yoshiharu
AU - Oliveira Mota, Guilherme
AU - Roberts, Barnaby
PY - 2020/11
Y1 - 2020/11
N2 - Given a positive integer s, a graph G s-Ramsey for a graph H, denoted G→(H)s, if every s-colouring of the edges of G contains a monochromatic copy of H. The s-colour size-Ramsey number ȓs(H) of a graph H is defined to be ȓs(H)= min{|E(G)|: G→(H)s}. We prove that, for all positive integers k and s, we have ȓs(Pnk)=O(n), where Pnk is the kth power of the n-vertex path Pn.
AB - Given a positive integer s, a graph G s-Ramsey for a graph H, denoted G→(H)s, if every s-colouring of the edges of G contains a monochromatic copy of H. The s-colour size-Ramsey number ȓs(H) of a graph H is defined to be ȓs(H)= min{|E(G)|: G→(H)s}. We prove that, for all positive integers k and s, we have ȓs(Pnk)=O(n), where Pnk is the kth power of the n-vertex path Pn.
KW - Powers of paths
KW - Ramsey
KW - Size-Ramsey
UR - http://www.scopus.com/inward/record.url?scp=85086875958&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2020.06.004
DO - 10.1016/j.jctb.2020.06.004
M3 - Article
SN - 0095-8956
VL - 145
SP - 359
EP - 375
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
ER -