The cost of perfection for matchings in graphs

DOI10.1016/J.DAM.2014.12.006MaRDI QIDQ299061zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(5)

• Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
• scientific article; zbMATH DE number 2114098 (Why is no real title available?)
• scientific article; zbMATH DE number 2114469 (Why is no real title available?)
• 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

Describes a project that uses

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)