On a Ramsey-type problem of Erdős and Pach
| Autor: | Eoin Long, Guus Regts, Viresh Patel, Ross J. Kang |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Degree (graph theory)
General Mathematics 010102 general mathematics Induced subgraph 0102 computer and information sciences Type (model theory) 01 natural sciences Complement (complexity) Combinatorics 010201 computation theory & mathematics Graph (abstract data type) 0101 mathematics Constant (mathematics) Mathematics |
| Zdroj: | Bulletin of the London Mathematical Society. 49:991-999 |
| ISSN: | 0024-6093 |
| DOI: | 10.1112/blms.12094 |
| Popis: | 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). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text