Regular Spanning Subgraphs of Bipartite Graphs of High Minimum Degree

Béla Csaba

Abstract


Let $G$ be a simple balanced bipartite graph on $2n$ vertices, $\delta = \delta(G)/n$, and $\rho_0={\delta + \sqrt{2 \delta -1} \over 2}$. If $\delta \ge 1/2$ then $G$ has a $\lfloor \rho_0 n \rfloor$-regular spanning subgraph. The statement is nearly tight.


Full Text: PDF