The multicolour size-Ramsey number of powers of paths

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

doi:10.1016/j.jctb.2020.06.004

The multicolour size-Ramsey number of powers of paths

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

University of Rhode Island
University of Birmingham
Universidade de São Paulo
The London School of Economics and Political Science

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

Abstract

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(P_n^k)=O(n), where P_n^k is the kth power of the n-vertex path P_n.

Original language	English
Pages (from-to)	359-375
Number of pages	17
Journal	Journal of Combinatorial Theory. Series B
Volume	145
DOIs	https://doi.org/10.1016/j.jctb.2020.06.004
Publication status	Published - Nov 2020
Externally published	Yes

Keywords

Powers of paths
Ramsey
Size-Ramsey

Access to Document

10.1016/j.jctb.2020.06.004

Cite this

@article{3e18a85a6d63432581871e87bc39d85b,

title = "The multicolour size-Ramsey number of powers of paths",

abstract = "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.",

keywords = "Powers of paths, Ramsey, Size-Ramsey",

author = "Jie Han and Matthew Jenssen and Yoshiharu Kohayakawa and Mota, \{Guilherme Oliveira\} and Barnaby Roberts",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2020",

month = nov,

doi = "10.1016/j.jctb.2020.06.004",

language = "English",

volume = "145",

pages = "359--375",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - The multicolour size-Ramsey number of powers of paths

AU - Han, Jie

AU - Jenssen, Matthew

AU - Kohayakawa, Yoshiharu

AU - Mota, Guilherme Oliveira

AU - Roberts, Barnaby

PY - 2020/11

Y1 - 2020/11

N2 - 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.

AB - 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.

KW - Powers of paths

KW - Ramsey

KW - Size-Ramsey

UR - https://www.scopus.com/pages/publications/85086875958

U2 - 10.1016/j.jctb.2020.06.004

DO - 10.1016/j.jctb.2020.06.004

M3 - Article

AN - SCOPUS:85086875958

SN - 0095-8956

VL - 145

SP - 359

EP - 375

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

The multicolour size-Ramsey number of powers of paths

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this