Characterizing graphs of small carving-width

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

doi:10.1007/978-3-642-31770-5

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings
Editors	Guohui Lin
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	360-370
Number of pages	11
ISBN (Electronic)	978-3-642-31770-5
ISBN (Print)	978-3-642-31769-9
DOIs	https://doi.org/10.1007/978-3-642-31770-5
Publication status	Published - 2012
Externally published	Yes
Event	6th International Conference on Combinatorial Optimization and Applications, COCOA 2012 - Banff, Canada Duration: 5 Aug 2012 → 9 Aug 2012 Conference number: 6

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7402
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Conference on Combinatorial Optimization and Applications, COCOA 2012
Abbreviated title	COCOA 2012
Country/Territory	Canada
City	Banff
Period	5/08/12 → 9/08/12

Access to Document

10.1007/978-3-642-31770-5

Cite this

Belmonte, R., van 't Hof, P., Kamiński, M., Paulusma, D., & Thilikos, D. M. (2012). Characterizing graphs of small carving-width. In G. Lin (Ed.), Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings (pp. 360-370). (Lecture Notes in Computer Science; Vol. 7402). Springer. https://doi.org/10.1007/978-3-642-31770-5

@inproceedings{f03179fe562f4747b37a08e9e33ea18d,

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

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 = "2012",

doi = "10.1007/978-3-642-31770-5",

language = "English",

isbn = "978-3-642-31769-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "360--370",

editor = "Guohui Lin",

booktitle = "Combinatorial Optimization and Applications",

address = "Germany",

note = "6th International Conference on Combinatorial Optimization and Applications, COCOA 2012, COCOA 2012 ; Conference date: 05-08-2012 Through 09-08-2012",

}

Belmonte, R, van 't Hof, P, Kamiński, M, Paulusma, D & Thilikos, DM 2012, Characterizing graphs of small carving-width. in G Lin (ed.), Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7402, Springer, Berlin, Heidelberg, pp. 360-370, 6th International Conference on Combinatorial Optimization and Applications, COCOA 2012, Banff, Alberta, Canada, 5/08/12. https://doi.org/10.1007/978-3-642-31770-5

Characterizing graphs of small carving-width. / Belmonte, Rémy; van 't Hof, Pim; Kamiński, Marcin et al.
Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings. ed. / Guohui Lin. Berlin, Heidelberg: Springer, 2012. p. 360-370 (Lecture Notes in Computer Science; Vol. 7402).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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.

N1 - Conference code: 6

PY - 2012

Y1 - 2012

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.

U2 - 10.1007/978-3-642-31770-5

DO - 10.1007/978-3-642-31770-5

M3 - Conference contribution

SN - 978-3-642-31769-9

T3 - Lecture Notes in Computer Science

SP - 360

EP - 370

BT - Combinatorial Optimization and Applications

A2 - Lin, Guohui

PB - Springer

CY - Berlin, Heidelberg

T2 - 6th International Conference on Combinatorial Optimization and Applications, COCOA 2012

Y2 - 5 August 2012 through 9 August 2012

ER -

Belmonte R, van 't Hof P, Kamiński M, Paulusma D, Thilikos DM. Characterizing graphs of small carving-width. In Lin G, editor, Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings. Berlin, Heidelberg: Springer. 2012. p. 360-370. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-31770-5

Characterizing graphs of small carving-width

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this