×

Regular spanning subgraphs of bipartite graphs of high minimum degree. (English) Zbl 1157.05322

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

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS