Characterizing Graphs of Small Carving-Width - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Applied Mathematics Year : 2013

Characterizing Graphs of Small Carving-Width


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.

Dates and versions

lirmm-00804730 , version 1 (26-03-2013)



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, 2013, pp.Electronic Edition. ⟨10.1016/j.dam.2013.02.036⟩. ⟨lirmm-00804730⟩
116 View
0 Download



Gmail Facebook X LinkedIn More