DIMACS TR: 2006-23

Note on regular spanning subgraphs of bipartite graphs of high minimum degree

Author: Bela Csaba


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

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-23.ps.gz
DIMACS Home Page