Lift Contractions
- Golovach, Petr A.
- Kaminski, Marcin
- Paulusma, Daniël
- Thilikos Touloupas, Dimitrios
DOIAbstract
We introduce and study a new containment relation in graphs - lift contractions. H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. We show that a graph contains every n-vertex graph as a lift contraction, if (1) its treewidth is large enough, or (2) its pathwidth is large enough and it is 2-connected, or (3) its order is large enough and its minimum degree is at least 3. © 2011 Elsevier B.V.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Add to ORKG