The size-Ramsey number of cubic graphs

David Conlon, Rajko Nenadov, Miloš Trujić

We show that the size-Ramsey number of any cubic graph with $n$ vertices is $O(n^{8/5})$, improving a bound of $n^{5/3+o(1)}$ due to Kohayakawa, Rödl, Schacht, and Szemerédi. The…