Hamiltonian Cycles in Tough (P4∪P1)‐Free Graphs

ABSTRACT

In 1973, Chvátal conjectured that there exists a constant such that every ‐tough graph on at least three vertices is Hamiltonian. This conjecture has inspired extensive research and has been verified for several special classes of graphs. Notably, Jung in 1978 proved that every 1‐tough ‐free graph on at least three vertices is Hamiltonian. However, the problem remains challenging even when restricted to graphs with no induced , the disjoint union of a path on four vertices and a one‐vertex path. In 2013, Nikoghosyan conjectured that every 1‐tough ‐free graph on at least three vertices is Hamiltonian. Later in 2015, Broersma remarked that “this question seems to be very hard to answer, even if we impose a higher toughness.” Instead he posed the following question: “Is the general conjecture of Chvátal's true for ‐free graphs?” We provide a positive answer to Broersma's question by establishing that every 23‐tough ‐free graph on at least three vertices is Hamiltonian.