Ramsey Numbers of Trails

09/02/2021

∙

by   Masatoshi Osumi, et al.

∙

0

∙

share

We initiate the study of Ramsey numbers of trails. Let k ≥ 2 be a positive integer. The Ramsey number of trails with k vertices is defined as the the smallest number n such that for every graph H with n vertices, H or the complete H contains a trail with k vertices. We prove that the Ramsey number of trails with k vertices is at most k and at least 2√(k)+Θ(1). This improves the trivial upper bound of ⌊ 3k/2⌋ -1.