# 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.