On the maximum even factor in weakly symmetric graphs

摘要

As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings, then they introduced the more general notion of even factor in weakly symmetric digraphs. Here we give a min-max formula for the maximum cardinality of an even factor. Our proof is purely combinatorial. We also provide a Gallai-Edmonds-type structure theorem for even factors. (C) 2004 Elsevier Inc. All rights reserved.