Orthogonal matchings revisited

Let G be a graph on n vertices, which is an edge-disjoint union of ms-factors, that is, s regular spanning subgraphs. Alspach first posed the problem that if there exists a matching M of m edges with exactly one edge from each 2-factor. Such a matching is called orthogonal because of applications in design theory. For s=2, so far the best known result is due to Stong in 2002, which states that if n≥3m−2, then there is an orthogonal matching. Anstee and Caccetta also asked if there is a matching M of m edges with exactly one edge from each s-factor? They answered yes for s≥3. In this paper, we get a better bound and prove that if s=2 and n≥22m+4.5 (note that 22≤2.825), then there is an orthogonal matching. We also prove that if s=1 and n≥3.2m−1, then there is an orthogonal matching, which improves the previous bound (3.79m).