Ramsey equivalence of Kn and Kn + Kn–1

Thomas F. Bloom; Anita Liebenau

Ramsey equivalence of K_n and K_n + K_n–1

Thomas F. Bloom, Anita Liebenau

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

5 Citations (Scopus)

116 Downloads (Pure)

Abstract

We prove that, for n ≥ 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 [10]. 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₃ is not Ramsey equivalent to K₃+K₂. We prove that any graph which witnesses this non-equivalence must contain K₆ as a subgraph.

Original language	English
Article number	#P3.4
Number of pages	12
Journal	Electronic Journal of Combinatorics
Volume	25
Issue number	3
Early online date	13 Jul 2018
Publication status	Published - Sept 2018

Keywords

Graph theory
Ramsey theory

Access to Document

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via EJC at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p4 . Please refer to any applicable terms of use of the publisher.
Final published version, 384 KB

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p4

Handle.net

Persistent link

Cite this

@article{5abb20fab83348448c47371052961991,

title = "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{\'o}, Zumstein, and Z{\"u}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.",

keywords = "Graph theory, Ramsey theory",

author = "Bloom, {Thomas F.} and Anita Liebenau",

year = "2018",

month = sep,

language = "English",

volume = "25",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "3",

}

TY - JOUR

T1 - Ramsey equivalence of Kn and Kn + Kn–1

AU - Bloom, Thomas F.

AU - Liebenau, Anita

PY - 2018/9

Y1 - 2018/9

N2 - 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.

AB - 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.

KW - Graph theory

KW - Ramsey theory

UR - http://www.scopus.com/inward/record.url?scp=85050987479&partnerID=8YFLogxK

M3 - Article (Academic Journal)

AN - SCOPUS:85050987479

SN - 1077-8926

VL - 25

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 3

M1 - #P3.4

ER -