The multicolour size-Ramsey number of powers of paths

Jie Han, Matthew Jenssen, Yoshiharu Yoshiharu Kohayakawa, Guilherme Oliveira Mota, Barnaby Roberts

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
40 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)359-375
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume145
Early online date27 Jun 2020
DOIs
Publication statusPublished - Nov 2020

Keywords

  • Ramsey
  • Size-Ramsey
  • Powers of paths

Fingerprint

Dive into the research topics of 'The multicolour size-Ramsey number of powers of paths'. Together they form a unique fingerprint.

Cite this