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:

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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-04}

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