In 1990 Erdős, Faudree, Rousseau and Schelp proved that for $k \ge 2$, every graph with $n \ge k+1$ vertices and $(k-1)(n-k+2)+\binom{k-2}{2}+1$ edges contains a subgraph of minimum degree $k$ on at most $n-\sqrt{n/6k^3}$ vertices. They conjectured that it is possible to remove at least $\epsilon_k n$ many vertices and remain with a subgraph of minimum degree $k$, for some $\epsilon_k>0$. We make progress towards their conjecture by showing that one can remove at least order of $\Omega(n/\log n)$ many vertices.
@article{10_37236_7167,
author = {Frank Mousset and Andreas Noever and Nemanja \v{S}kori\'c},
title = {Smaller subgraphs of minimum degree \(k\)},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {4},
doi = {10.37236/7167},
zbl = {1375.05062},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7167/}
}
TY - JOUR
AU - Frank Mousset
AU - Andreas Noever
AU - Nemanja Škorić
TI - Smaller subgraphs of minimum degree \(k\)
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/7167/
DO - 10.37236/7167
ID - 10_37236_7167
ER -
%0 Journal Article
%A Frank Mousset
%A Andreas Noever
%A Nemanja Škorić
%T Smaller subgraphs of minimum degree \(k\)
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7167/
%R 10.37236/7167
%F 10_37236_7167
Frank Mousset; Andreas Noever; Nemanja Škorić. Smaller subgraphs of minimum degree \(k\). The electronic journal of combinatorics, Tome 24 (2017) no. 4. doi: 10.37236/7167
