TR-2009-12

Restricted b-matchings in degree-bounded graphs

Kristóf Bérczi, László Végh



Abstract

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 K 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].


Bibtex entry:

@techreport{egres-09-12,
AUTHOR = {B{\'e}rczi, Krist{\'o}f and V{\'e}gh, L{\'a}szl{\'o}},
TITLE = {Restricted b-matchings in degree-bounded graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-12}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!