Smaller subgraphs of minimum degree k

2017/03/01 by Mousset, Frank, Noever, Andreas, Škorić, Nemanja
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1703.00273

Abstract

In 1990 Erdős, Faudree, Rousseau and Schelp proved that for k≥ 2, every graph with n≥ k+1 vertices and (k-1)(n-k+2)+\binomk-22+1 edges contains a subgraph of minimum degree k on at most n-√(n)/√(6k³) vertices. They conjectured that it is possible to remove at least ε_k n many vertices and remain with a subgraph of minimum degree k, for some ε_k>0. We make progress towards their conjecture by showing that one can remove at least Ω(n/log n) many vertices.

Related

• A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree k
• On the minimal degree condition of graphs implying some properties of subgraphs
• Minimum degree and the graph removal lemma
• Small subgraphs with large average degree
• Induced subgraphs with many repeated degrees