## Characterizing graphs of small carving-width

*Rémy Belmonte, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos*

*Discrete Applied Mathematics*, vol. 161, no. 13-14, pp. 1888-1893, 2013.

[__DOI__][__Preprint__]

A preliminary version of this paper appeared in the proceedings of COCOA 2012, the 6th Annual International Conference on Combinatorial Optimization and Applications (held on August 5-9, 2012 in Banff, Canada), *Lecture Notes in Computer Science*, vol. 7402, pp. 360-370, 2012.

[__DOI__]

### 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.