Induced subgraphs with many repeated degrees

2018/11/17 by Caro, Yair, Yuster, Raphael
#05C07 #05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1811.07221

Abstract

Erdős, Fajtlowicz and Staton asked for the least integer f(k) such that every graph with more than f(k) vertices has an induced regular subgraph with at least k vertices. Here we consider the following relaxed notions. Let g(k) be the least integer such that every graph with more than g(k) vertices has an induced subgraph with at least k repeated degrees and let h(k) be the least integer such that every graph with more than h(k) vertices has an induced subgraph with at least k maximum degree vertices. We obtain polynomial lower bounds for h(k) and g(k) and nontrivial linear upper bounds when the host graph has bounded maximum degree.

Related

• Large nearly regular induced subgraphs
• Large induced subgraphs with k vertices of almost maximum degree
• Every graph contains a linearly sized induced subgraph with all degrees odd
• Equating two maximum degrees
• Resolution of the Erdős-Sauer problem on regular subgraphs