DMS Combinatorics Seminar

Speaker: Songling Shan, Illinois State University/Auburn 

Title: 2-factors in 3/2-tough plane triangulations

Abstract: In 1956, Tutte proved the celebrated theorem that every 4-connected planar graph is hamiltonian. This result implies that every more than $\frac{3}{2}$-tough planar graph on at least three vertices is hamiltonian, and so has a 2-factor.  Owens in 1999 constructed non-hamiltonian maximal planar graphs of toughness smaller than $\frac{3}{2}$. In fact, the graphs Owens constructed do not even contain a 2-factor. Thus the toughness of exactly  $\frac{3}{2}$  is the only case left in asking about the existence of 2-factors in tough planar graphs. This question was also asked by  Bauer, Broersma, and  Schmeichel in a survey. We close this gap by showing that every maximal  $\frac{3}{2}$-tough plane graph on at least three vertices has a 2-factor.