Unions of 1-factors in $r$-graphs and overfull graphs

Abstract

We prove lower bounds for the fraction of edges of an $r$-graph which can be covered by the union of $k$ 1-factors. The special case $r=3$ yields some known results for cubic graphs. Furthermore, we introduce the concept of $k$-overfull-free $r$-graphs and achieve better bounds for these graphs.

14 pages, no figure, 1 table. To be published in Journal of Combinatorics. Difference from the previous version: We add the results on overfull graphs, stated in Chapter 4; Moreover, Corollary 3.2 is new

References in corpus (2)

• 1-factor and cycle covers of cubic graphs
• Petersen cores and the oddness of cubic graphs

Cited by in corpus (1)

• Partially normal 5-edge-colorings of cubic graphs