Skip to Main content Skip to Navigation
Journal articles

Characterizing Graphs of Small Carving-Width

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Dimitrios Thilikos <>
Submitted on : Tuesday, March 26, 2013 - 11:07:25 AM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM

Links full text




Rémy Belmonte, Pim van 'T Hof, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos. Characterizing Graphs of Small Carving-Width. Discrete Applied Mathematics, Elsevier, 2013, pp.Electronic Edition. ⟨10.1016/j.dam.2013.02.036⟩. ⟨lirmm-00804730⟩



Record views