A C-k-free 2-matching in an undirected graph is a simple 2-matching which does not contain cycles of length k or less. The complexity of finding the maximum C-k-free 2-matching in a given graph varies depending on k and the type of input graph. The case where k = 4 and the graph is bipartite, which is called the maximum square-free 2-matching problem in bipartite graphs, is well-solved. Previous results for this special case include min-max theorems, polynomial combinatorial algorithms, a linear programming formulation with dual integrality for a weighted version, and discrete convex structures.
In this paper, we further investigate the structure of square-free 2-matchings in bipartite graphs and present new decomposition theorems. These theorems serve as analogues of the Dulmage-Mendelsohn decomposition for matchings in bipartite graphs and the Edmonds-Gallai decomposition for matchings in nonbipartite graphs. We exhibit two canonical minimizers for the set function in the min-max formula, and a characterization of the maximum square-free 2-matchings with the aid of these canonical minimizers. (C) 2017 Elsevier B.V. All rights reserved.