###### Options

# The size-Ramsey number of powers of paths

Publikationstyp

Journal Article

Publikationsdatum

2019-07

Sprache

English

Institut

TORE-URI

Enthalten in

Volume

91

Issue

3

Start Page

290

End Page

299

Citation

Journal of Graph Theory 3 (91): 290-299 (2019-07)

Publisher DOI

Scopus ID

Given graphs G and H and a positive integer q, say that G is q-Ramsey for H, denoted G → (H) q , if every q-coloring of the edges of G contains a monochromatic copy of H. The size-Ramsey number (Formula presented.) of a graph H is defined to be (Formula presented.). Answering a question of Conlon, we prove that, for every fixed k, we have (Formula presented.), where P nk is the kth power of the n-vertex path P n (ie, 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.