An algorithm for finding a maximum tt-matching excluding complete partite subgraphs

For an integer tt and a fixed graph HH, we consider the problem of finding a maximum tt-matching not containing HH as a subgraph, which we call the HH-free tt-matching problem. This problem is a generalization of the problem of finding a maximum 22-matching with no short cycles, which has been well-studied as a natural relaxation of the Hamiltonian circuit problem. When HH is a complete graph Kt+1Kt+1 or a complete bipartite graph Kt,tKt,t, in 2010, Bérczi and Végh gave a polynomial-time algorithm for the HH-free tt-matching problem in simple graphs with maximum degree at most t+1t+1. A main contribution of this paper is to extend this result to the case when HH is a tt-regular complete partite graph. We also show that the problem is NP-complete when HH is a connected tt-regular graph that is not complete partite. Since it is known that, for a connected tt-regular graph HH, the degree sequences of all HH-free tt-matchings in a graph form a jump system if and only if HH is a complete partite graph, our results show that the polynomial-time solvability of the HH-free tt-matching problem is consistent with this condition.