Algebra and Combinatorics Seminar

Date: October 29, 2021

Time: 3:00PM - 4:00PM

Location: Zoom

Speaker: Elizabeth Grimm, Illinois State University

Title: Hamiltonicity of 3-tough (P2 ∪3P1)-free graphs

Abstract: Chv ́atal conjectured in 1973 the existence of some constant t such that all t-tough graphs with at least three vertices are Hamiltonian. While the conjecture has been proven for some special classes of graphs, it remains open in general. We say that a graph is (P2 ∪3P1)-free if it contains no induced subgraph isomorphic to P2 ∪3P1, where P2 ∪3P1 is the disjoint union of an edge and three isolated vertices. In this talk, we show that every 3-tough (P2 ∪3P1)-free graph with at least three vertices is Hamiltonian.