Skip to main content

Research Repository

Advanced Search

Characterizing graphs of small carving-width

Belmonte, R.; van 't Hof, P.; Kaminski, M.; Paulusma, D.; Thilikos, D.M.

Authors

R. Belmonte

P. van 't Hof

M. Kaminski

D.M. Thilikos



Contributors

Guohui Lin
Editor

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.

Citation

Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Characterizing graphs of small carving-width. In G. Lin (Ed.), Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings (360-370). https://doi.org/10.1007/978-3-642-31770-5_32

Publication Date 2012
Deposit Date Mar 11, 2013
Pages 360-370
Series Title Lecture notes in computer science
Series Number 7402
Series ISSN 0302-9743,1611-3349
Book Title Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings.
ISBN 9783642317699
DOI https://doi.org/10.1007/978-3-642-31770-5_32
Public URL https://durham-repository.worktribe.com/output/1156160
Additional Information Series: Lecture Notes in Computer Science, Volume 7402