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.

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2003},
NUMBER	=	{TR-2003-02}

}