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.

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.


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.