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 metadatas
Contributor : Dimitrios M. Thilikos <>
Submitted on : Tuesday, March 26, 2013 - 11:07:25 AM
Last modification on : Friday, October 5, 2018 - 9:14:01 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