Induced Subgraphs with Many Distinct Degrees

Bhargav Narayanan, István Tomon

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)110-123
Number of pages14
JournalCombinatorics Probability and Computing
Volume27
Issue number1
DOIs
StatePublished - Jan 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Induced Subgraphs with Many Distinct Degrees'. Together they form a unique fingerprint.

Cite this