Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs

• Main Authors: Mou, Gao, Pasechnik, Dmitrii V.
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2017
• 主題: 2K2-free graphs; t-tough graphs
• 在線閱讀: https://hdl.handle.net/10356/83360; http://hdl.handle.net/10220/42557

We show that an edge-dominating cycle in a 2K22K2-free graph can be found in polynomial time; this implies that every 1k−11k−1-tough 2K22K2-free graph admits a kk-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...