On the maximum even factor in weakly symmetric graphs

Gyula Pap, László Szegő

Published in:
Journal of combinatorial theory Ser B. 91 (2004) 201-213.


As a common generalization of matchings and matroid intersection, W.H. Cunningham and J.F. 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.

Bibtex entry:

AUTHOR = {Pap, Gyula and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE = {On the maximum even factor in weakly symmetric graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2003},
NUMBER = {TR-2003-02}

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