Publisher DOI: | 10.1002/jgt.22432 | Title: | The size-Ramsey number of powers of paths | Language: | English | Authors: | Clemens, Dennis ![]() Jenssen, Matthew Kohayakawa, Yoshiharu Morrison, Natasha Mota, Guilherme Oliveira Reding, Damian Roberts, Barnaby |
Issue Date: | Jul-2019 | Source: | Journal of Graph Theory 3 (91): 290-299 (2019-07) | Journal or Series Name: | Journal of graph theory | Abstract (english): | 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. |
URI: | http://hdl.handle.net/11420/2755 | ISSN: | 0364-9024 | Institute: | Mathematik E-10 | Document Type: | Article |
Appears in Collections: | Publications without fulltext |
Show full item record
Add Files to Item
Note about this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.