Logo image
Se connecter
Characterizing Graphs of Small Carving-Width
Article de revue   Open Access   Avec comité de lecture

Characterizing Graphs of Small Carving-Width

Rémy Belmonte, Pim van 'T Hof, Marcin Kamiński, Daniël Paulusma et Dimitrios M. Thilikos
Discrete Applied Mathematics
23/03/2013

Résumé

Obstruction set Carving-width Immersion
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.

Fichiers et liens (2)

url
Find in HALAfficher
url
https://doi.org/10.1016/j.dam.2013.02.036Afficher
Published (Version of record) Ouvrir

Indicateurs

1 Consultations de la notice

Détails

Logo image