Covering dense $r$-graphs by perfect matchings
For a matching-covered graph $G$, let $τ(G)$ denote the minimum number of perfect matchings needed to cover all edges of $G$. An $r$-regular graph $G$ is said to be an $r$-graph if $|\partial(X)|\geq r$ for each odd set $X\subseteq V(G)$, where $\partial(X)$ denotes the set of edges with precisely one end in $X$. The generalized Berge conjecture, which was proposed by Mazzuoccolo (J. Graph Theory, 73 (2013) 377-385) and equivalent to the generalized Berge-Fulkerson Conjecture posed by Seymour (Proc. London Math. Soc., 38 (1979) 423-460), states that $τ(G)\leq 2r-1$ for every $r$-graph $G$, while the 1-factorization conjecture, first explicitly formulated by Chetwynd and Hilton (Proc. London Math. Soc., 50 (1985) 193-206), states that $τ(G)=r$ for every $r$-graph $G$ of order $2n$ with $r\ge n$. These conjectures are still open. In this paper, we obtain the following two main results: 1. Let $G$ be an $r$-graph of order $2n$. If $r\ge n$, then $τ(G)\leq 2r-1$, which implies that the generalized Berge conjecture holds for $r\ge n$, and a linear upper bound of $τ(G)$ in the 1-factorization conjecture is obtained. 2. Let $G$ be an $r$-graph of order $2n$. If $r\ge 2n/3$, then $τ(G)\leq 4r$, which implies that a linear upper bound of $τ(G)$ in the generalized Berge conjecture is obtained if $r\geq 2n/3$. Our main approach combines equitable proper edge-colorings, matching extension techniques, and applications of Edmonds's perfect matching polytope theorem.
Authors
- Danyi Li (ORCID: https://orcid.org/0000-0003-1138-9181)
- Weigen Yan (ORCID: https://orcid.org/0000-0002-2657-1210)
- Jingchao Lai
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24019
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint