TR-2003-02

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.



Abstract

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:

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


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