Logo image
Sign in
Lift-contractions
Journal article   Open access   Peer reviewed

Lift-contractions

Petr A. Golovach, Daniël Paulusma, Marcin Kamiski and Dimitrios M. Thilikos
European Journal of Combinatorics, Vol.35, pp.286-296
2014

Abstract

edge contractions edge lifts immersions treewidth
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 struc-ture of graphs with an excluded lift-contraction.
url
Find in HALView
url
https://doi.org/10.1016/j.ejc.2013.06.026View
Published (Version of record) Open

Metrics

1 Record Views

Details

Logo image