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).
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
|Look up in GoogleScholar|