Mubayi, Dhruv


Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

\begin{conjecture} For every $\epsilon > 0$ and every positive integer $k$, there exists $r_0 = r_0(\epsilon,k)$ so that every simple $r$-regular graph $G$ with $r \ge r_0$ has a $k$-regular subgraph $H$ with $|V(H)| \ge (1- \epsilon) |V(G)|$. \end{conjecture}

Keywords: regular; subgraph

Syndicate content