Skip to Main content Skip to Navigation
Journal articles

Outerplanar obstructions for matroid pathwidth

Abstract : For each non-negative integer k, we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most k. Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083516
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, November 17, 2014 - 1:52:13 PM
Last modification on : Monday, May 4, 2020 - 9:42:03 AM
Document(s) archivé(s) le : Friday, April 14, 2017 - 1:44:39 PM

File

mpath.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki. Outerplanar obstructions for matroid pathwidth. Discrete Mathematics, Elsevier, 2013, 315-316, pp.95-101. ⟨10.1016/j.disc.2013.10.007⟩. ⟨lirmm-01083516⟩

Share

Metrics

Record views

131

Files downloads

440