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_32

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: Chapter in Book/Report/Conference proceeding › Conference contribution

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)
Title of host publication	Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings
Pages	360-370
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-31770-5_32
State	Published - 2012
Event	6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012 - Banff, AB, Canada Duration: Aug 5 2012 → Aug 9 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7402 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012
Country/Territory	Canada
City	Banff, AB
Period	8/5/12 → 8/9/12

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Belmonte, R., Van 't Hof, P., Kamiński, M., Paulusma, D., & Thilikos, D. M. (2012). Characterizing graphs of small carving-width. In Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings (pp. 360-370). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7402 LNCS). https://doi.org/10.1007/978-3-642-31770-5_32

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, Proceedings. 2012. p. 360-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7402 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Belmonte, R, Van 't Hof, P, Kamiński, M, Paulusma, D & Thilikos, DM 2012, Characterizing graphs of small carving-width. in Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7402 LNCS, pp. 360-370, 6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012, Banff, AB, Canada, 8/5/12. https://doi.org/10.1007/978-3-642-31770-5_32

Belmonte R, Van 't Hof P, Kamiński M, Paulusma D, Thilikos DM. Characterizing graphs of small carving-width. In Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings. 2012. p. 360-370. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31770-5_32

@inproceedings{2ff55db7ef2e40189df281f6818547ad,

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

language = "English (US)",

isbn = "9783642317699",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "360--370",

booktitle = "Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings",

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

}

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.

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.

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:84864992393

SN - 9783642317699

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 360

EP - 370

BT - Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings

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

Y2 - 5 August 2012 through 9 August 2012

ER -

Characterizing graphs of small carving-width

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this