Unions of 1-factors in $r$-graphs
Ligang Jin · arXiv (Cornell University) · 2015
The generalized Berge-Fulkerson conjecture states that every $r$-graph has $2r$ 1-factors such that each edge is contained in precisely two of them. This conjecture is shown to be equivalent to the statement that every $r$-graph can be covered by $2r-1$ 1-factors. In this paper, we obtain, for any positive integers $r\geq 3$ and $k$, a lower bound of the fraction of edges covered by $k$ 1-factors in $r$-graphs. Moreover, it was announced by Kaiser, Kr\'al and Norine [Unions of perfect matching in cubic graphs, Topics in Discrete Mathematics, in: Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 225 - 230] and completely proved by Mazzuoccolo [Covering a cubic graph with perfect matchings, Discrete Mathematics 313 (2013) 2292 - 2296] a lower bound for the fraction of edges covered by $k$ 1-factors in bridgeless cubic graphs (i.e., 3-graphs). Our result extends this to $r$-graphs with $r\geq 3$.