Golovach, P.A. and Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (2011) 'Lift contractions.', Electronic notes in discrete mathematics., 38 (1). pp. 407-412.
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.
|Keywords:||Contractions, Treewidth, Immersions, Edge lifts.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.endm.2011.09.066|
|Record Created:||07 Dec 2011 14:51|
|Last Modified:||03 Apr 2013 16:21|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|