Department of

December 2018 January 2019February 2019Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su MoTuWe Th Fr Sa 1 1 2 3 4 5 1 2 2 3 4 5 6 7 8 6 7 8 9 10 11 12 3 4 5 6 7 8 9 9 10 11 12 13 14 15 13 14 15 16 17 18 19 10 11 12 13 14 15 16 16 17 18 19 20 21 22 20 21 22 23 24 25 26 17 181920 21 22 23 23 24 25 26 27 28 29 27 28 29 30 31 24 25 26 27 28 30 31

Tuesday, January 15, 2019

**Abstract:** Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize this by proving for $k\le(2r+1)/3$ that every $(2r+1)$-regular graph with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. The restrictions on $k$ and on the number of cut-edges are sharp. We characterize the graphs with exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor. (Joint work with Alexandr V. Kostochka, Andr\'e Raspaud, Bjarne Toft, and Dara Zirlin.)

We determine the maximum guaranteed size of a $2$-regular subgraph in a $3$-regular $n$-vertex graph. In particular, we prove that every multigraph with maximum degree $3$ and exactly $c$ cut-edges has a $2$-regular subgraph that omits at most $(3n-2m+c-1)/2$ vertices (or $0$ for $3$-regular graphs without cut-edges). The bound is sharp; we describe the extremal multigraphs. (Joint work with Ilkyoo Choi, Ringi Kim, Alexandr V. Kostochka, and Boram Park.)