Premium
The size‐Ramsey number of powers of paths
Author(s) -
Clemens Dennis,
Jenssen Matthew,
Kohayakawa Yoshiharu,
Morrison Natasha,
Mota Guilherme Oliveira,
Reding Damian,
Roberts Barnaby
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22432
Subject(s) - combinatorics , mathematics , ramsey's theorem , vertex (graph theory) , discrete mathematics , monochromatic color , graph , ramsey theory , botany , biology
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 numberr ˆ ( H ) of a graph H is defined to be r ˆ ( H ) = min { ∣ E ( G ) ∣ : G → ( H ) 2 } . Answering a question of Conlon, we prove that, for every fixed k , we have r ˆ ( P n k ) = O ( n ) , where P n k is the k th 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.