P.A. Golovach
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 | Mar 28, 2024 |
Journal | European Journal of Combinatorics |
Print ISSN | 0195-6698 |
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 |
Files
Published Journal Article
(601 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
This is an open access article under the CC BY license (http://creativecommons.org/licenses/
by/3.0/).
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search