Skip to main content

Research Repository

Advanced Search

Characterizing graphs of small carving-width

Belmonte, R.; Hof, van 't P.; Kaminski, M.; Paulusma, D.; Thilikos, D.M.

Characterizing graphs of small carving-width Thumbnail


Authors

R. Belmonte

van 't P. Hof

M. Kaminski

D.M. Thilikos



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., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036

Journal Article Type Article
Publication Date Sep 1, 2013
Deposit Date Dec 20, 2014
Publicly Available Date Jan 6, 2015
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 161
Issue 13-14
Pages 1888-1893
DOI https://doi.org/10.1016/j.dam.2013.02.036
Keywords Immersion, Carving-width, Obstruction set.
Public URL https://durham-repository.worktribe.com/output/1415088

Files

Accepted Journal Article (283 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Discrete applied 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 Discrete applied mathematics, 161, 13-14, 2013, 10.1016/j.dam.2013.02.036





You might also like



Downloadable Citations