A new upper bound on the minimum degree of minimal Ramsey graphs

Abstract

We prove that $s_r(K_{k+1})=O(k^3{r}^3{\log }^{3}k)$, where $s_r(K_k)$ is 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 $K_k$, whereas no proper subgraph of $G$ has this property.

arXiv admin note: text overlap with arXiv:2008.02474