On the minimum degree of minimal Ramsey graphs for multiple colours

Jacob Fox, Audrey Grinshpun, Anita Liebenau, Yury Person, Tibor Szabo

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

A graph G is r-Ramsey for a graph H, denoted by G→(H)r, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property. Let sr(H) denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H. The study of the parameter s2 was initiated by Burr, Erdos, and Lovász in 1976 when they showed that for the clique s2(Kk)=(k-1)2. In this paper, we study the dependency of sr(Kk) on r and show that, under the condition that k is constant, sr(Kk)=r2•polylog r. We also give an upper bound on sr(Kk) which is polynomial in both r and k, and we show that cr2ln rsr(K3) ≤ Cr2ln2r for some constants c, C>0.
Original languageEnglish
Pages (from-to)64-82
Number of pages19
JournalJournal of Combinatorial Theory, Series B
Volume120
DOIs
Publication statusPublished - 2016

Keywords

  • Erdos-Rogers function
  • Graph theory
  • Minimal Ramsey graphs
  • Minimum degree
  • Ramsey theory

Cite this