| Authors |
|
| Publication date |
2017
|
| Journal |
Bulletin of the London Mathematical Society
|
| Volume | Issue number |
49 | 6
|
| Pages (from-to) |
991-999
|
| Organisations |
-
Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
|
| 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
|
|
Permalink to this page
|