A graph is $d$-bounded if its maximum degree is at most $d$. We apply the Ore-Ryser Theorem on $f$-factors in bipartite graphs to obtain conditions for the extension of a $2$-bounded subgraph to a $2$-factor in a bipartite graph. As consequences, we prove that every matching in the $5$-dimensional hypercube extends to a $2$-factor, and we obtain conditions for this property in general regular bipartite graphs. For example, to show that every matching in a regular $n$-vertex bipartite graph extends to a $2$-factor, it suffices to show that all matchings with fewer than $n/3$ edges extend to $2$-factors.
@article{10_37236_3594,
author = {Jennifer Vandenbussche and Douglas B. West},
title = {Extensions to 2-factors in bipartite graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3594},
zbl = {1295.05188},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3594/}
}
TY - JOUR
AU - Jennifer Vandenbussche
AU - Douglas B. West
TI - Extensions to 2-factors in bipartite graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3594/
DO - 10.37236/3594
ID - 10_37236_3594
ER -
%0 Journal Article
%A Jennifer Vandenbussche
%A Douglas B. West
%T Extensions to 2-factors in bipartite graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3594/
%R 10.37236/3594
%F 10_37236_3594
Jennifer Vandenbussche; Douglas B. West. Extensions to 2-factors in bipartite graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3594
