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

DOI10.1016/J.DAM.2007.02.002MaRDI QIDQ2370435zbMATH OpenOpenAlexFDO

Authors D. Bauer, Hajo Broersma, Nathan Kahl, Aurora Morgana, E. Schmeichel, Thomas Surowiec

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

(perfect) matching\(D\)-graphdeficiencyextreme setTutte set

Mathematics Subject Classification ID

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

Recommendations

• Tutte sets in graphs I: Maximal tutte sets and D-graphs
• An algebraic matching algorithm
• On upper bounds for parameters related to the construction of special maximum matchings
• scientific article; zbMATH DE number 19225
• An algorithm for finding a maximum t-matching excluding complete partite subgraphs

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2016836 (Why is no real title available?)
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• Some simplified NP-complete graph problems
• Splitters and barriers in open graphs having a perfect internal matching
• Structuring the elementary components of graphs having a perfect internal matching.
• The Factorization of Linear Graphs
• Tutte sets in graphs I: Maximal tutte sets and D-graphs
• Tutte type theorems for graphs having a perfect internal matching
• TWO THEOREMS IN GRAPH THEORY

Cited in

(6)

• Generalizing \(D\)-graphs
• Toughness in graphs -- a survey
• Graph toughness from Laplacian eigenvalues
• Tutte sets in graphs I: Maximal tutte sets and D-graphs
• On maximum graphs in Tutte polynomial posets
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370435)