Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\) (Q1658778): Difference between revisions

Summary: We prove that, for \(n\geqslant 4\), the graphs \(K_n\) and \(K_n+K_{n-1}\) are Ramsey equivalent. That is, if \(G\) is such that any red-blue colouring of its edges creates a monochromatic \(K_n\) then it must also possess a monochromatic \(K_n+K_{n-1}\). This resolves a conjecture of \textit{T. Szabó} et al. [J. Graph Theory 64, No. 2, 150--164 (2010; Zbl 1209.05151)]. The result is tight in two directions. Firstly, it is known that \(K_n\) is not Ramsey equivalent to \(K_n+2K_{n-1}\). Secondly, \(K_3\) is not Ramsey equivalent to \(K_3+K_2\). We prove that any graph which witness this non-equivalence must contain \(K_6\) as a subgraph.