Transversals and bipancyclicity in bipartite graph families

Abstract

A bipartite graph is called bipancyclic if it contains cycles of every even length from four up to the number of vertices in the graph. A theorem of Schmeichel and Mitchem states that for $n\ge 4$, every balanced bipartite graph on $2n$ vertices in which each vertex in one color class has degree greater than $\frac{n}{2}$ and each vertex in the other color class has degree at least $\frac{n}{2}$ is bipancyclic. We prove a generalization of this theorem in the setting of graph transversals. Namely, we show that given a family $\mathcal{G}$ of $2n$ bipartite graphs on a common set $X$ of $2n$ vertices with a common balanced bipartition, if each graph of $\mathcal{G}$ has minimum degree greater than $\frac{n}{2}$ in one color class and minimum degree at least $\frac{n}{2}$ in the other color class, then there exists a cycle on $X$ of each even length $4\le \ell \le 2n$ that uses at most one edge from each graph of $\mathcal{G}$. We also show that given a family $\mathcal{G}$ of $n$ bipartite graphs on a common set $X$ of $2n$ vertices meeting the same degree conditions, there exists a perfect matching on $X$ that uses exactly one edge from each graph of $\mathcal{G}$.

14 pages, 6 figures