Restricted b-matchings in degree-bounded graphs
Bérczi, K. & Végh, L. A.
(2010-06-09 - 2010-06-11)
Restricted b-matchings in degree-bounded graphs
[Paper]. The 14th Conference on Integer Programming & Combinatorial Optimization (IPCO XIV), Lausanne, Switzerland, CHE.
(2010-06-09 - 2010-06-11)
Restricted b-matchings in degree-bounded graphs
[Paper]. The 14th Conference on Integer Programming & Combinatorial Optimization (IPCO XIV), Lausanne, Switzerland, CHE.
We present a min-max formula and a polynomial time algorithm for a slight generalization of the following problem: in a simple undirected graph in which the degree of each node is at most t + 1, find a maximum t-matching containing no member of a list of forbidden K t,t and K t + 1 subgraphs. An analogous problem for bipartite graphs without degree bounds was solved by Makai [15], while the special case of finding a maximum square-free 2-matching in a subcubic graph was solved in [1].