The multicolour size-Ramsey number of powers of paths
Han, J., Jenssen, M., Kohayakawa, Y., Mota, G. O. & Roberts, B.
(2020).
The multicolour size-Ramsey number of powers of paths.
Journal of Combinatorial Theory. Series B,
145, 359 - 375.
https://doi.org/10.1016/j.jctb.2020.06.004
Given a positive integer s, a graph G is 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 rˆs(H) of a graph H is defined to be rˆs(H)=min{|E(G)|:G→(H)s}. We prove that, for all positive integers k and s, we have rˆs(Pnk)=O(n), where Pnk is the kth power of the n-vertex path Pn.
| Item Type | Article |
|---|---|
| Copyright holders | © 2020 Elsevier Inc. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.jctb.2020.06.004 |
| Date Deposited | 10 Jun 2022 |
| URI | https://researchonline.lse.ac.uk/id/eprint/115334 |
Explore Further
- https://www.scopus.com/pages/publications/85086875958 (Scopus publication)