The cost of perfection for matchings in graphs

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

zbMATH Keywords

cubic graphsperfect matchingsregular bipartite graphstriangle meshes

Mathematics Subject Classification ID

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

• Blossom-Quad

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