P.A. Golovach
Lift Contractions
Golovach, P.A.; Kamiński, M.; Paulusma, D.; Thilikos, D.M.
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.
Presentation Conference Type | Conference Paper (published) |
---|---|
Publication Date | Dec 1, 2011 |
Deposit Date | Dec 6, 2011 |
Publicly Available Date | Jan 14, 2015 |
Journal | Electronic Notes in Discrete Mathematics |
Print ISSN | 1571-0653 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 38 |
Issue | 1 |
Pages | 407-412 |
DOI | https://doi.org/10.1016/j.endm.2011.09.066 |
Keywords | Contractions, Treewidth, Immersions, Edge lifts. |
Public URL | https://durham-repository.worktribe.com/output/1157561 |
Files
Accepted Journal Article
(393 Kb)
PDF
Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Electronic notes in discrete mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Electronic notes in discrete mathematics, 38/1/, 2011, 10.1016/j.endm.2011.09.066
You might also like
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
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