Large induced subgraphs with k vertices of almost maximum degree

2017/05/24 by Girão, António, Popielarz, Kamil
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1705.08998

Abstract

In this note we prove that for every integer k, there exist constants g₁(k) and g₂(k) such that the following holds. If G is a graph on n vertices with maximum degree Δ then it contains an induced subgraph H on at least n - g₁(k)√Δ vertices, such that H has k vertices of the same degree of order at least Δ(H)-g₂(k). This solves a conjecture of Caro and Yuster up to the constant g₂(k).

Related

• Equating two maximum degrees
• Induced subgraphs with many repeated degrees
• Disjoint induced subgraphs of the same order and size
• Large nearly regular induced subgraphs
• Every graph contains a linearly sized induced subgraph with all degrees odd