Characterizing graphs of small carving-width

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

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, December). Characterizing graphs of small carving-width

• Presentation Conference Type: Conference Paper (published)
• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Print ISSN: 0302-9743
• 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