Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Abstract

Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field F, the list needs to contain only finitely many F-representable matroids, due to the well-quasi-ordering of F-representable matroids of bounded branch-width under taking matroid minors [J.F. Geelen, A.M.H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F-representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2