Department of

Mathematics


Seminar Calendar
for events the day of Tuesday, January 15, 2019.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
    December 2018           January 2019          February 2019    
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We 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 18 19 20 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

2:00 pm in 243 Altgeld Hall,Tuesday, January 15, 2019

Cut-edges and Regular Subgraphs in Odd-degree Regular Graphs

Douglas B. West (Zhejiang Normal University and University of Illinois)

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.)