A note on the minimum degree of minimal Ramsey graphs

Anurag Bishnoi, Thomas Lesgourgues

Research output: Contribution to journalArticleScientificpeer-review

53 Downloads (Pure)

Abstract

In this note, we briefly rectify oversights in the works of several authors on sr (Kk), the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph G such that any r-colouring of the edges of G contains a monochromatic Kk, whereas no proper subgraph of G has this property. We show that sr (Kk+1) = O(k3 r3 ln3 k), improving the best known bounds when k ≥ 8 and k2 ≤ r ≤ O(k4/ ln6 k).

Original languageEnglish
Pages (from-to)65-69
Number of pages5
JournalAustralasian Journal of Combinatorics
Volume92
Issue number1
Publication statusPublished - 2025

Fingerprint

Dive into the research topics of 'A note on the minimum degree of minimal Ramsey graphs'. Together they form a unique fingerprint.

Cite this