Lift-contractions

Golovach, P.A.; Paulusma, D.; Kaminski, M.; Thilikos, D.M.

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.

Citation

Golovach, P., Paulusma, D., Kaminski, M., & Thilikos, D. (2014). Lift-contractions. European Journal of Combinatorics, 35, 286-296. https://doi.org/10.1016/j.ejc.2013.06.026

• Journal Article Type: Article
• Publication Date: Jan 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 8, 2015
• Journal: European Journal of Combinatorics
• Print ISSN: 0195-6698
• Electronic ISSN: 1095-9971
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 35
• Pages: 286-296
• DOI: https://doi.org/10.1016/j.ejc.2013.06.026
• Public URL: https://durham-repository.worktribe.com/output/1447825