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

✍ Scribed by Bianca Spille; László Szegő

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 122 KB
• Volume: 46
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10175

✦ Synopsis

Abstract

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. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 93–102, 2004