Characterizing graphs of small carving-width

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publication6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings
EditorsGuohui Lin
Place of PublicationBerlin, Heidelberg
PublisherSpringer Singapore
Pages360-370
Number of pages11
ISBN (Electronic)978-3-642-31770-5
ISBN (Print)978-3-642-31769-9
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event6th International Conference on Combinatorial Optimization and Applications, COCOA 2012 - Banff, Canada
Duration: 5 Aug 20129 Aug 2012
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7402
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Combinatorial Optimization and Applications, COCOA 2012
Abbreviated titleCOCOA 2012
CountryCanada
CityBanff
Period5/08/129/08/12

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

Cite this