On a Ramsey-type problem of Erdős and Pach
| Authors | |
|---|---|
| Publication date | 2015 |
| Journal | Electronic Notes in Discrete Mathematics |
| Event | The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015 |
| Volume | Issue number | 49 |
| Pages (from-to) | 821-827 |
| Organisations |
|
| Abstract | Erdős and Pach (1983) asked if there is some constant C>0C>0 such that for any graph G on Ckln k vertices either G or its complement G¯ has an induced subgraph on k vertices with minimum degree at least 1/2(k−1). They showed that the above statement holds with Ck2 in place of Ckln k but that it does not hold with Ckln k/ln lnk. We show that it holds with Ckln2 k, answering their question up to a ln k factor. |
| Document type | Article |
| Note |
Proceedings title: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015: Bergen, Norway, August 31 - September 4 Publisher: Elsevier Place of publication: Amsterdam Editors: J. Nešetřil, O. Serra, J.A. Telle |
| Language | English |
| Related publication | On a Ramsey-type problem of Erdős and Pach |
| Published at | https://doi.org/10.1016/j.endm.2015.06.049 |
| Permalink to this page | |