Belmonte, R. and van 't Hof, P. and Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (2012) 'Characterizing graphs of small carving-width.', in Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings. Berlin ; Heidelberg: Springer, pp. 360-370. Lecture notes in computer science. (7402).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | Full text not available from this repository. |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-31770-5_32 |
| Date accepted: | No date available |
| Date deposited: | No date available |
| Date of first online publication: | 2012 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
