Smaller Subgraphs of Minimum Degree $k

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...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2017-10, Vol.24 (4)
Main Authors: Mousset, Frank, Noever, Andreas, Škorić, Nemanja
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1077-8926
1077-8926
DOI:10.37236/7167