Skip to main content

Research Repository

Advanced Search

Lift Contractions

Golovach, P.A.; Kamiński, M.; Paulusma, D.; Thilikos, D.M.

Lift Contractions Thumbnail


Authors

P.A. Golovach

M. Kamiński

D.M. Thilikos



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.

Citation

Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. Lift Contractions

Presentation Conference Type Conference Paper (published)
Publication Date Dec 1, 2011
Deposit Date Dec 6, 2011
Publicly Available Date Jan 14, 2015
Journal Electronic Notes in Discrete Mathematics
Print ISSN 1571-0653
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 38
Issue 1
Pages 407-412
DOI https://doi.org/10.1016/j.endm.2011.09.066
Keywords Contractions, Treewidth, Immersions, Edge lifts.
Public URL https://durham-repository.worktribe.com/output/1157561

Files

Accepted Journal Article (393 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Electronic notes in discrete mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Electronic notes in discrete mathematics, 38/1/, 2011, 10.1016/j.endm.2011.09.066






You might also like



Downloadable Citations