R. Belmonte
Characterizing graphs of small carving-width
Belmonte, R.; van 't Hof, P.; Kaminski, M.; Paulusma, D.; Thilikos, D.M.
Authors
P. van 't Hof
M. Kaminski
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
D.M. Thilikos
Contributors
Guohui Lin
Editor
Abstract
We characterize all graphs that have carving-width at most k for k = 1,2,3. In particular, we show that a graph has carving-width at most 3 if and only if it has maximum degree at most 3 and treewidth at most 2. This enables us to identify the immersion obstruction set for graphs of carving-width at most 3.
Citation
Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Characterizing graphs of small carving-width. In G. Lin (Ed.), Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings (360-370). https://doi.org/10.1007/978-3-642-31770-5_32
Publication Date | 2012 |
---|---|
Deposit Date | Mar 11, 2013 |
Pages | 360-370 |
Series Title | Lecture notes in computer science |
Series Number | 7402 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings. |
ISBN | 9783642317699 |
DOI | https://doi.org/10.1007/978-3-642-31770-5_32 |
Public URL | https://durham-repository.worktribe.com/output/1156160 |
Additional Information | Series: Lecture Notes in Computer Science, Volume 7402 |
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