An algorithm for finding a maximum t‐matching excluding complete partite subgraphs

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