A note on the minimum degree of minimal Ramsey graphs
Anurag Bishnoi (TU Delft - Discrete Mathematics and Optimization)
Thomas Lesgourgues (University of Waterloo)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
In this note, we briefly rectify oversights in the works of several authors on sr (Kk), the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph G such that any r-colouring of the edges of G contains a monochromatic Kk, whereas no proper subgraph of G has this property. We show that sr (Kk+1) = O(k3 r3 ln3 k), improving the best known bounds when k ≥ 8 and k2 ≤ r ≤ O(k4/ ln6 k).
help_outline