On a Ramsey-type problem of Erdős and Pach
Affirmatively answering a question of Erd˝os and Pach from 1983, we show for some constant C > 0 that for any graph G on Ck ln k vertices either G or its complement G has an induced subgraph on k vertices with minimum degree at least 1 2 (k − 1).
| Hlavní autoři: | , , , |
|---|---|
| Médium: | Journal article |
| Vydáno: |
London Mathematical Society
2017
|