From edge-dominating cycles to $k$-walks and Hamilton prisms of $2K_2$-free graphs

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.

Back to all abstracts