The cost of perfection for matchings in graphs

DOI10.1016/J.DAM.2014.12.006zbMATH Open1339.05153arXiv1204.2727OpenAlexW2949906226MaRDI QIDQ299061FDOQ299061

Authors: E. V. Brazil, Celina M. H. de Figueiredo, Guilherme D. Da Fonseca, Diana Sasaki 

Publication date: 22 June 2016

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

Abstract: Perfect matchings and maximum weight matchings are two fundamental combinatorial structures. We consider the ratio between the maximum weight of a perfect matching and the maximum weight of a general matching. Motivated by the computer graphics application in triangle meshes, where we seek to convert a triangulation into a quadrangulation by merging pairs of adjacent triangles, we focus mainly on bridgeless cubic graphs. First, we characterize graphs that attain the extreme ratios. Second, we present a lower bound for all bridgeless cubic graphs. Third, we present upper bounds for subclasses of bridgeless cubic graphs, most of which are shown to be tight. Additionally, we present tight bounds for the class of regular bipartite graphs.

Full work available at URL: https://arxiv.org/abs/1204.2727

Recommendations

• 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
• A new lower bound on the number of perfect matchings in cubic graphs
• An improved linear bound on the number of perfect matchings in cubic graphs
• scientific article; zbMATH DE number 2114098

zbMATH Keywords

perfect matchingscubic graphsregular bipartite graphstriangle meshes

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Maximum matching and a polyhedron with 0,1-vertices
• The hunting of a snark with total chromatic number 5
• Every planar map is four colorable
• A theorem on tait colorings with an application to the generalized Petersen graphs
• The equivalence of two conjectures of Berge and Fulkerson
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Blocking and anti-blocking pairs of polyhedra
• Converting triangulations to quadrangulations
• Blossom-Quad: a non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm
• The smallest 2-connected cubic bipartite planar nonhamiltonian graph
• Every generalized Petersen graph has a Tait coloring
• Efficient algorithms for Petersen's matching theorem
• Title not available (Why is that?)
• Perfect matching for biconnected cubic graphs in \(O(n \log ^{2} n)\) time
• Randomly matchable graphs

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
• On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching
• On the ratio between maximum weight perfect matchings and maximum weight matchings in grids

Uses Software

• Blossom-Quad

This page was built for publication: The cost of perfection for matchings in graphs

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