Characterizing graphs of small carving-width

Rémy Belmonte, Pim Van't Hof, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1888-1893
Number of pages6
JournalDiscrete Applied Mathematics
Issue number13-14
StatePublished - Sep 2013


  • Carving-width
  • Immersion
  • Obstruction set

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Characterizing graphs of small carving-width'. Together they form a unique fingerprint.

Cite this