On a Ramsey-type problem of Erdős and Pach

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes

External organisations

  • Radboud University
  • University of Amsterdam


In this paper we show that there exists a constant C>0 such that for any graph G on Cklnk vertices either G or its complement G¯ has an induced subgraph on k vertices with minimum degree at least ½(k−1). This affirmatively answers a question of Erdős and Pach from 1983.


Original languageEnglish
Pages (from-to)991-999
Number of pages9
JournalBulletin of the London Mathematical Society
Issue number6
Early online date6 Oct 2017
Publication statusPublished - 1 Dec 2017


  • 05C55 (primary), 05D10, 05D40 (secondary)