Lift-contractions

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

doi:10.1016/j.ejc.2013.06.026

Lift-contractions

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

Computer Science

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

Abstract

We introduce and study a partial order on graphs-lift-contractions. A graph H is a lift-contraction of a graph G if H can be obtained from G by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to contain every n-vertex graph as a lift-contraction and describe the structure of graphs with an excluded lift-contraction.

Original language	English (US)
Pages (from-to)	286-296
Number of pages	11
Journal	European Journal of Combinatorics
Volume	35
DOIs	https://doi.org/10.1016/j.ejc.2013.06.026
State	Published - Jan 2014

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2013.06.026

Cite this

@article{d94ebce766a6456f98228aecfb9d8cbc,

title = "Lift-contractions",

abstract = "We introduce and study a partial order on graphs-lift-contractions. A graph H is a lift-contraction of a graph G if H can be obtained from G by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to contain every n-vertex graph as a lift-contraction and describe the structure of graphs with an excluded lift-contraction.",

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

year = "2014",

month = jan,

doi = "10.1016/j.ejc.2013.06.026",

language = "English (US)",

volume = "35",

pages = "286--296",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Lift-contractions

AU - Golovach, Petr A.

AU - Paulusma, Daniël

AU - Kamiński, Marcin

AU - Thilikos, Dimitrios M.

PY - 2014/1

Y1 - 2014/1

N2 - We introduce and study a partial order on graphs-lift-contractions. A graph H is a lift-contraction of a graph G if H can be obtained from G by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to contain every n-vertex graph as a lift-contraction and describe the structure of graphs with an excluded lift-contraction.

AB - We introduce and study a partial order on graphs-lift-contractions. A graph H is a lift-contraction of a graph G if H can be obtained from G by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to contain every n-vertex graph as a lift-contraction and describe the structure of graphs with an excluded lift-contraction.

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

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

U2 - 10.1016/j.ejc.2013.06.026

DO - 10.1016/j.ejc.2013.06.026

M3 - Article

AN - SCOPUS:84882607325

SN - 0195-6698

VL - 35

SP - 286

EP - 296

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Lift-contractions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this