From edge-dominating cycles to $k$-walks and Hamilton prisms of $2K_2$-free graphs
Mou Gao
Nanyang Technological University
Dmitrii Pasechnik
Department of Computer Science, The University of Oxford, UK
PDF
Minisymposium: GENERAL SESSION TALKS
Content: We show that every $\frac{1}{k-1}$-tough $2K_2$-free graph admits a $k$-walk, and it can be found in polynomial time. For this class of graphs, this proves a long-standing conjecture due to Jackson and Wormald (1990). Furthermore, we prove that every $(1+\epsilon)$-tough $2K_2$-free graph is prism-Hamiltonian. And, we also get some similar results of some other graphs.