Characterizing graphs of small carving-width

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

doi:10.1016/j.dam.2013.02.036

Characterizing graphs of small carving-width

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	1888-1893
Number of pages	6
Journal	Discrete Applied Mathematics
Volume	161
Issue number	13-14
DOIs	https://doi.org/10.1016/j.dam.2013.02.036
State	Published - Sep 2013

Keywords

Carving-width
Immersion
Obstruction set

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2013.02.036

Cite this

@article{08b2a3d604c94e4182ef8c624f95e036,

title = "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.",

keywords = "Carving-width, Immersion, Obstruction set",

author = "R{\'e}my Belmonte and {Van't Hof}, Pim and Marcin Kami{\'n}ski and Dani{\"e}l Paulusma and Thilikos, {Dimitrios M.}",

year = "2013",

month = sep,

doi = "10.1016/j.dam.2013.02.036",

language = "English (US)",

volume = "161",

pages = "1888--1893",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "13-14",

}

TY - JOUR

T1 - Characterizing graphs of small carving-width

AU - Belmonte, Rémy

AU - Van't Hof, Pim

AU - Kamiński, Marcin

AU - Paulusma, Daniël

AU - Thilikos, Dimitrios M.

PY - 2013/9

Y1 - 2013/9

N2 - 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.

AB - 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.

KW - Carving-width

KW - Immersion

KW - Obstruction set

UR - http://www.scopus.com/inward/record.url?scp=84878278423&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878278423&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2013.02.036

DO - 10.1016/j.dam.2013.02.036

M3 - Article

AN - SCOPUS:84878278423

SN - 0166-218X

VL - 161

SP - 1888

EP - 1893

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 13-14

ER -

Characterizing graphs of small carving-width

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this