paper

Graphs with arbitrary Ramsey number and connectivity

arXiv:2311.01887

Abstract

The Ramsey number $r (G)$ of a graph $G$ is the minimum number $N$ such that any red-blue colouring of the edges of $K_{N}$ contains a monochromatic copy of $G$ . Pavez-SignÃ©, Piga and Sanhueza-Matamala proved that for any function $n \leq f (n) \leq r (K_{n})$ , there is a sequence of connected graphs $(G_{n})_{n \in N}$ with $∣ V (G_{n}) ∣ = n$ such that $r (G_{n}) = I^ (f (n))$ and conjectured that $G_{n}$ can additionally have arbitrarily large connectivity. In this note we prove their conjecture.