Answers are grounded in this paper and cite their sources.
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 |∂(X)|≥ r for each odd set X⊆ V(G), where ∂(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)≤ 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≥ 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≥ n, then τ(G)≤ 2r-1, which implies that the generalized Berge conjecture holds for r≥ 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≥ 2n/3, then τ(G)≤ 4r, which implies that a linear upper bound of $τ(G)$ in the generalized Berge conjecture is obtained if r≥ 2n/3. Our main approach combines equitable proper edge-colorings, matching extension techniques, and applications of Edmonds's perfect matching polytope theorem.
No takes yet. Share an insight, caveat, or question.
Lai et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: