Ear-slicing for matchings in hypergraphs

DOI10.1007/S00373-020-02228-YMaRDI QIDQ2657060zbMATH OpenOpenAlexFDO

Authors András Sebö

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

antifactorcovering for hypergraphsear-theoremfactor-criticalgeneral factormatchingpacking for hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study when a given edge of a factor-critical graph is contained in a matching avoiding exactly one, pregiven vertex of the graph. We then apply the results to always partition the vertex-set of a $3$-regular, $3$-uniform hypergraph into at most one triangle (hyperedge of size $3$) and edges (subsets of size $2$ of hyperedges), corresponding to the intuition, and providing new insight to triangle and edge packings of Cornu'ejols' and Pulleyblank's. The existence of such a packing can be considered to be a hypergraph variant of Petersen's theorem on perfect matchings, and leads to a simple proof for a sharpening of Lu's theorem on antifactors of graphs.

Recommendations

• Matching in 3-uniform hypergraphs
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in balanced hypergraphs---a combinatorial approach
• The partition of a uniform hypergraph into pairs of dependent hyperedges
• Nearly perfect matchings in regular simple hypergraphs

Cites work

• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• Matching theory
• Packing subgraphs in a graph
• The Factorization of Linear Graphs

Cited in

(2)

• An O ( VE ) algorithm for ear decompositions of matching-covered graphs
• Slicing an ear using prune-and-search

This page was built for publication: Ear-slicing for matchings in hypergraphs

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