Matching structure and the matching lattice

DOI10.1016/0095-8956(87)90021-9zbMath0659.05081OpenAlexW1998621342MaRDI QIDQ1112071

No author found.

Publication date: 1987

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(87)90021-9

zbMATH Keywords

latticeconvex hullperfect matchingspolyhedral combinatoricsedge-colorationlinear hull

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Graph theory (05C99)

Related Items (74)

A note on tight cuts in matching-covered graphs ⋮ Optimizing Sparsity over Lattices and Semigroups ⋮ On Dyadic Fractional Packings of $T$-Joins ⋮ Gallai-Edmonds decomposition as a pruning technique ⋮ On cycle-nice claw-free graphs ⋮ On Two Unsolved Problems Concerning Matching Covered Graphs ⋮ The cocycle lattice of binary matroids. II ⋮ A note on the lattice of 2-matroid-intersections ⋮ Generating bricks ⋮ On 2-extendable abelian Cayley graphs ⋮ Total dual dyadicness and dyadic generating sets ⋮ Bicritical graphs without removable edges ⋮ Removable ears of 1-extendable graphs ⋮ The 2-matching lattice of a graph ⋮ Thin edges in braces ⋮ A generalization of Little's theorem on Pfaffian orientations ⋮ Equivalence classes in matching covered graphs ⋮ Minimal braces ⋮ On extremal nonsolid bricks ⋮ Matching covered graphs with three removable classes ⋮ Matching connectivity: on the structure of graphs with perfect matchings ⋮ A superlinear bound on the number of perfect matchings in cubic bridgeless graphs ⋮ A characterization of minimal non-Seymour graphs ⋮ On Hilbert bases of cuts ⋮ A characterization of nonfeasible sets in matching covered graphs ⋮ Generating simple near‐bipartite bricks ⋮ Resonance graphs on perfect matchings of graphs on surfaces ⋮ Some snarks are worse than others ⋮ New approximation results on graph matching and related problems ⋮ The cubic vertices of solid minimal bricks ⋮ Minimum degree of minimal \((n-10)\)-factor-critical graphs ⋮ How to build a brick ⋮ Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs ⋮ Pfaffian orientations for a type of bipartite graph ⋮ Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs ⋮ Minimal bricks have many vertices of small degree ⋮ Birkhoff--von Neumann Graphs that are PM-Compact ⋮ Excluding Minors in Cubic Graphs ⋮ Disjoint Odd Cycles in Cubic Solid Bricks ⋮ The lattices of matroid bases and exact matroid bases ⋮ The lattice of cycles of an undirected graph ⋮ Face-width of Pfaffian braces and polyhex graphs on surfaces ⋮ An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs ⋮ Cubic bridgeless graphs and braces ⋮ Minimally non-Pfaffian graphs ⋮ Pfaffian labelings and signs of edge colorings ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ A note on the \(f\)-factor-lattice of bipartite graphs ⋮ The Cubic Vertices of Minimal Bricks ⋮ A lower bound on the number of removable ears of 1-extendable graphs ⋮ The Even Cycle Problem for Directed Graphs ⋮ Digraphs of directed treewidth one ⋮ The perfect matching polytope and solid bricks ⋮ An improved linear bound on the number of perfect matchings in cubic graphs ⋮ Minimal bricks ⋮ Brace generation ⋮ Direct sum of distributive lattices on the perfect matchings of a plane bipartite graph ⋮ Construction for bicritical graphs and \(k\)-extendable bipartite graphs ⋮ On the number of dissimilar pfaffian orientations of graphs ⋮ Spanning trees of 3-uniform hypergraphs ⋮ Laminar tight cuts in matching covered graphs ⋮ On essentially 4-edge-connected cubic bricks ⋮ 2-extendability of toroidal polyhexes and Klein-bottle polyhexes ⋮ K ₄ -free and C6¯-free Planar Matching Covered Graphs ⋮ \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks ⋮ Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions ⋮ Ear decompositions of join covered graphs ⋮ Relations between global forcing number and maximum anti-forcing number of a graph ⋮ Colouring non-even digraphs ⋮ Optimal ear decompositions of matching covered graphs and bases for the matching lattice ⋮ On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph ⋮ Matching theory and Barnette's conjecture ⋮ Extending matchings in graphs: A survey ⋮ Sparse representation of vectors in lattices and semigroups

Cites Work

• Unnamed Item
• Brick decompositions and the matching rank of graphs
• Matching theory
• Convex polyhedra of doubly stochastic matrices. IV
• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Rank of maximum matchings in a graph
• The NP-Completeness of Edge-Coloring
• Ear Decompositions of Elementary Graphs and GF2-rank of Perfect Matchings
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• On the structure of factorizable graphs
• The Factorization of Linear Graphs

This page was built for publication: Matching structure and the matching lattice