On the minimum degree of minimal Ramsey graphs for cliques versus cycles

Anurag Bishnoi, Simona Boyadzhiyska, Dennis Clemens, Pranshu Gupta, Thomas Lesgourgues, Anita Liebenau

Research output: Contribution to journalArticleScientificpeer-review

5 Downloads (Pure)


A graph G is said to be q-Ramsey for a q-tuple of graphs (H1,..., Hq), denoted by G →q (H1,..., Hq), if every q-edge-coloring of G contains a monochromatic copy of Hi in color i for some i ε [q]. Let sq(H1,..., Hq) denote the smallest minimum degree of G over all graphs G that are minimal q-Ramsey for (H1,..., Hq) (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdos, and Lovasz, who determined its value precisely for a pair of cliques. Over the past two decades the parameter sq has been studied by several groups of authors, their main focus being on the symmetric case, where Hi ≅ H for all i ε [q]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine s2(H1, H2) when (H1, H2) is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on sq(Cℓ,..., Cℓ, Kt,..., Kt) in terms of the size of the cliques t, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.

Original languageEnglish
Pages (from-to)25-50
Number of pages26
JournalSIAM Journal on Discrete Mathematics
Issue number1
Publication statusPublished - 2023

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • cliques
  • cycles
  • minimum degree
  • Ramsey theory


Dive into the research topics of 'On the minimum degree of minimal Ramsey graphs for cliques versus cycles'. Together they form a unique fingerprint.

Cite this