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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2013, pp.Electronic Edition. 〈http://authors.elsevier.com/sd/article/S0166218X13001236〉. 〈10.1016/j.dam.2013.02.036〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804730
Contributeur : Dimitrios M. Thilikos <>
Soumis le : mardi 26 mars 2013 - 11:07:25
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

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. 〈http://authors.elsevier.com/sd/article/S0166218X13001236〉. 〈10.1016/j.dam.2013.02.036〉. 〈lirmm-00804730〉

Partager

Métriques

Consultations de la notice

107