Induced Subgraphs with Many Distinct Degrees

TY - JOUR

T1 - Induced Subgraphs with Many Distinct Degrees

AU - Narayanan, Bhargav

AU - Tomon, István

N1 - Publisher Copyright: Copyright © 2017 Cambridge University Press.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Let hom(G) denote the size of the largest clique or independent set of a graph G. In 2007, Bukh and Sudakov proved that every n-vertex graph G with 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 every n-vertex graph G with hom(G) = O(nϵ ), where ϵ > 0 is a fixed constant. Here, we answer their question in the affirmative and show that every graph G on n vertices 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 fixed k ϵ N, that if an n-vertex graph G contains no induced subgraph with k distinct degrees, then hom(G)≥n/(k - 1) - o(n); this bound is essentially best possible.

AB - Let hom(G) denote the size of the largest clique or independent set of a graph G. In 2007, Bukh and Sudakov proved that every n-vertex graph G with 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 every n-vertex graph G with hom(G) = O(nϵ ), where ϵ > 0 is a fixed constant. Here, we answer their question in the affirmative and show that every graph G on n vertices 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 fixed k ϵ N, that if an n-vertex graph G contains no induced subgraph with k distinct degrees, then hom(G)≥n/(k - 1) - o(n); this bound is essentially best possible.

UR - http://www.scopus.com/inward/record.url?scp=85026511824&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85026511824&partnerID=8YFLogxK

U2 - https://doi.org/10.1017/S0963548317000256

DO - https://doi.org/10.1017/S0963548317000256

M3 - Article

SN - 0963-5483

VL - 27

SP - 110

EP - 123

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 1

ER -