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

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Radboud University
  • University of Amsterdam

Abstract

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.

Details

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

Keywords

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