Lift Contractions

Petr A. Golovach; Marcin Kamiński; Daniël Paulusma; Dimitrios M. Thilikos

doi:10.1016/j.endm.2011.09.066

Lift Contractions

Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	407-412
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	38
DOIs	https://doi.org/10.1016/j.endm.2011.09.066
State	Published - Dec 1 2011

Keywords

Contractions
Edge lifts
Immersions
Treewidth

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2011.09.066

Cite this

@article{981f4a77d7014e80b579ca296c262cf6,

title = "Lift Contractions",

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.",

keywords = "Contractions, Edge lifts, Immersions, Treewidth",

author = "Golovach, {Petr A.} and Marcin Kami{\'n}ski and Dani{\"e}l Paulusma and Thilikos, {Dimitrios M.}",

year = "2011",

month = dec,

day = "1",

doi = "10.1016/j.endm.2011.09.066",

language = "English (US)",

volume = "38",

pages = "407--412",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Lift Contractions

AU - Golovach, Petr A.

AU - Kamiński, Marcin

AU - Paulusma, Daniël

AU - Thilikos, Dimitrios M.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

KW - Contractions

KW - Edge lifts

KW - Immersions

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=82955216095&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=82955216095&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2011.09.066

DO - 10.1016/j.endm.2011.09.066

M3 - Article

AN - SCOPUS:82955216095

SN - 1571-0653

VL - 38

SP - 407

EP - 412

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Lift Contractions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this