Generalizing Tutte's theorem and maximal non-matchable graphs

DOI10.1016/j.disc.2013.05.015zbMath1281.05108OpenAlexW2051151547MaRDI QIDQ390291

Kok Bin Wong, Cheng Yeaw Ku

Publication date: 23 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2013.05.015

zbMATH Keywords

matching polynomialGallai-Edmonds decompositionmaximal non-matchable graphsTutte's theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (3)

Extensions of barrier sets to nonzero roots of the matching polynomial ⋮ Gallai-Edmonds structure theorem for weighted matching polynomial ⋮ A refined Gallai-Edmonds structure theorem for weighted matching polynomials

Cites Work

• Properties of \(\theta\)-super positive graphs
• Extensions of barrier sets to nonzero roots of the matching polynomial
• Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
• Matching theory
• Problems in algebraic combinatorics
• Algebraic matching theory
• Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover
• Gallai-Edmonds structure theorem for weighted matching polynomial
• Theory of monomer-dimer systems

This page was built for publication: Generalizing Tutte's theorem and maximal non-matchable graphs