Characterizing graphs of small carving-widthRémy Belmonte, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos
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.