Loading...
Please wait, while we are loading the content...
Similar Documents
Induced Subgraphs With Many Distinct Degrees
| Content Provider | Scilit |
|---|---|
| Author | Narayanan, Bhargav Tomon, István |
| Copyright Year | 2017 |
| Description | Let hom(G) denote the size of the largest clique or independent set of a graphG. In 2007, Bukh and Sudakov proved that everyn-vertex graphGwith hom(G) =O(logn) contains an induced subgraph with $Ω(n^{1/2}$) distinct degrees, and raised the question of deciding whether an analogous result holds for everyn-vertex graphGwith hom(G) $=O(n^{ϵ}$), whereϵ> 0 is a fixed constant. Here, we answer their question in the affirmative and show that every graphGonnvertices contains an induced subgraph with $Ω((n/hom(G))^{1/2}$) distinct degrees. We also prove a stronger result for graphs with large cliques or independent sets and show, for any fixedk∈ ℕ, that if ann-vertex graphGcontains no induced subgraph withkdistinct degrees, then hom(G)⩾n/(k− 1) −o(n); this bound is essentially best possible. |
| Related Links | http://arxiv.org/pdf/1609.01677 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/61BD845CFC0B7D2AFCA32103FF07FCA5/S0963548317000256a.pdf/div-class-title-induced-subgraphs-with-many-distinct-degrees-div.pdf |
| Ending Page | 123 |
| Page Count | 14 |
| Starting Page | 110 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548317000256 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 1 |
| Volume Number | 27 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2018-01-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Primary 05d10 Secondary 05c07 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
