Tutte seminar - Bruce Richter

Long cycles in 2-factors of 3-regular graphs

Abstract:

Petersen's Theorem says that every 2-connected, 3-regular graph has a 2-factor (i.e., a set of disjoint cycles whose union contains all the vertices). We are interested in finding the longest cycle that occurs in a 2-factor of such a graph. (For example, the Petersen graph, there is a cycle of length 9, but it is not in any 2-factor. The longest cycle in a 2-factor of the Petersen graph has length 5.) We prove that there are arbitrarily large 3-connected, 3-regular graphs with no 2-factor having a cycle of length more than 16 and that every 2-connected, 3-regular graph with at least 12 vertices has a 2-factor having a cycle of length at least 7. Obviously, lots of natural questions remain. 

Joint work with André Kundgen.