2020/02/23 by Bradshaw, Peter · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2002.10014
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 ≥ 4, every balanced bipartite graph on 2n vertices in which each vertex in one color class has degree greater than (n)/(2) and each vertex in the other color class has degree at least (n)/(2) is bipancyclic. We prove a generalization of this theorem in the setting of graph transversals. Namely, we show that given a family 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 (n)/(2) in one color class and minimum degree at least (n)/(2) in the other color class, then there exists a cycle on X of each even length 4 ≤ ℓ ≤ 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.