Journal of Combinatorics

Volume 11 (2020)

Number 3

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

Pages: 457 – 473

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n3.a2

Authors

Ligang Jin (Department of Mathematics, Zhejiang Normal University, Jinhua, China)

Eckhard Steffen (Paderborn Center for Advanced Studies, and Institute for Mathematics, Paderborn University, Paderborn, Germany)

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.

Keywords

$r$-graphs, $1$-factors, overfull graphs

Full Text (PDF format)

The first-named author was supported by the grants NSFC 11801522 and QJD 1803023.

Received 1 September 2018

Accepted 22 July 2019

Published 11 May 2020