Toughness, 2-factors and Hamiltonian cycles in $2K_2$-free graphs

Katsuhiro Ota, Masahiro Sanka

Published 2021-03-11Version 1

A graph $G$ is called a $2K_2$-free graph if it does not contain $2K_2$ as an induced subgraph. In 2014, Broersma et al.\ showed that every 25-tough $2K_2$-free graph with at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. On the other hand, Kratsch et al.\ showed that for any $t <\frac{3}{2}$ there exists a $t$-tough split graph without 2-factors (also, it is a $2K_2$-free graph). In this paper, we present two results. First, we show that every $\frac{3}{2}$-tough $2K_2$-free graph has a $2$-factor. This result is sharp by the result in split graphs. Second, we show that every 2-tough $2K_2$-free graph is Hamiltonian, which was conjectured by Mou and Pasechnik.