TR-2002-04

A Gallai--Edmonds-type structure theorem for path-matchings.

Bianca Spille, László Szegő

Published in:
Journal of graph theory. 46 (2004) 93-102

As a generalization of matchings, Cunningham and Geelen introduced the notion of path-matchings. We give a structure theorem for path-matchings which generalizes the fundamental Gallai-Edmonds structure theorem for matchings. Our proof is purely combinatorial.

Bibtex entry:

@techreport{egres-02-04,

AUTHOR	=	{Spille, Bianca and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE	=	{A {G}allai--{E}dmonds-type structure theorem for path-matchings.},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-04}

}