Journal article
Ramsey equivalence of Kn and Kn + Kn−1
- Abstract:
-
We prove that, for n ≥ 4, the graphs Kn and Kn + Kn−1 are Ramsey equivalent. That is, if G is such that any red-blue colouring of its edges creates a monochromatic Kn then it must also possess a monochromatic Kn + Kn−1. This resolves a conjecture of Szabó, Zumstein, and Zürcher [10].
The result is tight in two directions. Firstly, it is known that Kn is not Ramsey equivalent to Kn + 2Kn−1. Secondly, K3 is not Ramsey equivalent to K3 + K2. We prove that any graph which witnesses this non-equivalence must contain K6 as a subgraph.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 384.3KB, Terms of use)
-
- Publisher copy:
- 10.37236/7554
Authors
- Publisher:
- Electronic Journal of Combinatorics
- Journal:
- Electronic Journal of Combinatorics More from this journal
- Volume:
- 25
- Issue:
- 3
- Article number:
- P3.4
- Publication date:
- 2018-07-13
- Acceptance date:
- 2018-04-30
- DOI:
- EISSN:
-
1077-8926
- Language:
-
English
- Keywords:
- Pubs id:
-
1193530
- Local pid:
-
pubs:1193530
- Deposit date:
-
2021-08-31
- ARK identifier:
Terms of use
- Copyright holder:
- Bloom and Liebenau
- Copyright date:
- 2018
- Rights statement:
- Copyright The authors. Released under the CC BY license (International 4.0).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record