On the graphic matroid parity problem
type: Item
instance of: scholarly article
title: On the graphic matroid parity problem
zbMATH Open document ID: 1029.05027
DOI: 10.1016/S0095-8956(02)00045-X
author: Zoltán Szigeti
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-17T00:00:00Z
review text: A new proof is given of the min-max theorem of Lovász on the graphic matroid problem. The proof is based on existing proofs of Tutte's matching theorem. A matroid is graphic if it is the cycle matroid of some graph. Given a graph \(G\) and a partition \(V\) of its edge set into pairs, \((G, V)\) is called a \(v\)-graph, and a \(v\)-forest of \((G, V)\) is a forest of \(G\) consisting of \(v\)-pairs in \(V\). The graphic matroid problem is to find the maximum number of \(v\)-pairs in a \(v\)-forest in a \(v\)-graph.
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 1965031
zbMATH Keywords: graphic matroid
MaRDI profile type: Publication
cites work: Perfect matchings of a graph
cites work: Q3258698
cites work: Paths, Trees, and Flowers
cites work: Q5684698
cites work: Complexity of Matroid Property Algorithms
cites work: Q3912491
cites work: Q3896158
cites work: Matroid matching and some applications
cites work: Matching theory
cites work: Über die Maximalzahl kreuzungsfreier H-Wege
cites work: A new characterization of the maximum genus of a graph
cites work: Matroid theory and its applications in electric network theory and in statics
cites work: Q3840349
cites work: Graph factors
description: scientific article; zbMATH DE number 1965031