A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem

DOI10.1016/j.ejc.2011.01.009zbMath1229.05234OpenAlexW2040959127MaRDI QIDQ641542

Douglas B. West

Publication date: 24 October 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.01.009

zbMATH Keywords

matching, bigraph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Related Items (15)

Ramsey number of paths and connected matchings in Ore-type host graphs ⋮ Edge guards for polyhedra in three-space ⋮ Irreducible triangulations of surfaces with boundary ⋮ Graphs with maximal induced matchings of the same size ⋮ Co-density and fractional edge cover packing ⋮ The matchings and spectral radius of graphs involving minimum degree ⋮ Computing the least-core and nucleolus for threshold cardinality matching games ⋮ Linear hypergraphs with large transversal number and maximum degree two ⋮ Densities, Matchings, and Fractional Edge-Colorings ⋮ Trees and acyclic matrices over arbitrary fields ⋮ A characterization of graphs with given maximum degree and smallest possible matching number ⋮ Matching and edge-connectivity in graphs with given maximum degree ⋮ The maximum spectral radius of \(t\)-connected graphs with bounded matching number ⋮ The maximal A_α-spectral radius of graphs with given matching number ⋮ A generalization of Petersen's matching theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Perfect matchings of a graph
• On Representatives of Subsets
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs

This page was built for publication: A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem