- On a Ramsey-type problem of Erdős and Pach
- Electronic Notes in Discrete Mathematics
- Pages (from-to)
- Document type
- Faculty of Science (FNWI)
- Korteweg-de Vries Institute for Mathematics (KdVI)
- 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.
- go to publisher's site
- Proceedings title: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015: Bergen, Norway,
August 31 - September 4
Place of publication: Amsterdam
Editors: J. Nešetřil, O. Serra, J.A. Telle
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.