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 Szabó, Zumstein, and Zürcher.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 witnesses this non-equivalence must contain $K_6$ as a subgraph.
@article{10_37236_7554,
author = {Thomas F. Bloom and Anita Liebenau},
title = {Ramsey equivalence of {\(K_n\)} and {\(K_n+K_{n-1}\)}},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {3},
doi = {10.37236/7554},
zbl = {1393.05185},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7554/}
}
TY - JOUR
AU - Thomas F. Bloom
AU - Anita Liebenau
TI - Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\)
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/7554/
DO - 10.37236/7554
ID - 10_37236_7554
ER -
%0 Journal Article
%A Thomas F. Bloom
%A Anita Liebenau
%T Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\)
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7554/
%R 10.37236/7554
%F 10_37236_7554
Thomas F. Bloom; Anita Liebenau. Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\). The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/7554
