| 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 |
-
Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
|
| 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
|