Article ID Journal Published Year Pages File Type
6423923 Electronic Notes in Discrete Mathematics 2011 6 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,