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 
Type: (wissenschaftlicher) Artikel
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

104
Last Week
0
Last month
0
checked on Oct 26, 2020

Google ScholarTM

Check

Add Files to Item

Note about this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.