The cost of perfection for matchings in graphs
From MaRDI portal
Publication:299061
DOI10.1016/j.dam.2014.12.006zbMath1339.05153arXiv1204.2727OpenAlexW2949906226MaRDI QIDQ299061
E. V. Brazil, Diana Sasaki, Guilherme Dias da Fonseca, Celina M. Herrera de Figueiredo
Publication date: 22 June 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.2727
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Perfect graphs (05C17) Signed and weighted graphs (05C22)
Related Items (2)
On the ratio between maximum weight perfect matchings and maximum weight matchings in grids ⋮ On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- The smallest 2-connected cubic bipartite planar nonhamiltonian graph
- Converting triangulations to quadrangulations
- The hunting of a snark with total chromatic number 5
- Every generalized Petersen graph has a Tait coloring
- Efficient Algorithms for Petersen's Matching Theorem
- Blossom-Quad: A non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm
- The equivalence of two conjectures of Berge and Fulkerson
- Perfect Matching for Biconnected Cubic Graphs in O(n log2 n) Time
- Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
- Every planar map is four colorable
- Randomly matchable graphs
- Maximum matching and a polyhedron with 0,1-vertices
- A theorem on tait colorings with an application to the generalized Petersen graphs
- Blocking and anti-blocking pairs of polyhedra
This page was built for publication: The cost of perfection for matchings in graphs
