On a Ramsey-type problem of Erdős and Pach
| Authors | |
|---|---|
| Publication date | 2017 |
| Journal | Bulletin of the London Mathematical Society |
| Volume | Issue number | 49 | 6 |
| Pages (from-to) | 991-999 |
| Organisations |
|
| Abstract | We affirmatively answer a question of Erdős and Pach from 1983 by showing the following: there is some constant C>0 such that for any graph G on Ck ln k vertices either G or its complement has an induced subgraph on k vertices with minimum degree at least 0.5(k-1). |
| Document type | Article |
| Note | A preliminary version (with three authors) appeared in the Proceedings of EuroComb 2015 |
| Language | English |
| Related publication | On a Ramsey-type problem of Erdős and Pach |
| Published at |
https://doi.org/10.1112/blms.12094
(Final published version)
|
| Permalink to this page | |