Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419602 | Discrete Applied Mathematics | 2013 | 6 Pages |
Abstract
We characterize all graphs that have carving-width at most kk for k=1,2,3k=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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rémy Belmonte, Pim van ’t Hof, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos,