Tutte sets in graphs. II: The complexity of finding maximum Tutte sets

DOI10.1016/j.dam.2007.02.002zbMath1119.05086OpenAlexW2012519220MaRDI QIDQ2370435

Douglas Bauer, Hajo J. Broersma, Nathan Kahl, Thomas M. Surowiec, Edward F. Schmeichel, Aurora Morgana

Publication date: 26 June 2007

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

Full work available at URL: https://research.utwente.nl/en/publications/tutte-sets-in-graphs-ii-the-complexity-of-finding-maximum-tutte-sets(f7a29e83-948c-47f6-aea3-d74c45040c88).html

zbMATH Keywords

deficiencyextreme setTutte set\(D\)-graph(perfect) matching

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 (4)

Generalized \(D\)-graphs for nonzero roots of the matching polynomial ⋮ Graph toughness from Laplacian eigenvalues ⋮ Generalizing \(D\)-graphs ⋮ Toughness in graphs -- a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Some simplified NP-complete graph problems
• Structuring the elementary components of graphs having a perfect internal matching.
• Tutte type theorems for graphs having a perfect internal matching
• TWO THEOREMS IN GRAPH THEORY
• Tutte sets in graphs I: Maximal tutte sets and D-graphs
• Maximum matching and a polyhedron with 0,1-vertices
• The Factorization of Linear Graphs

This page was built for publication: Tutte sets in graphs. II: The complexity of finding maximum Tutte sets