Obstructions for matroids of pathwidth at most k and graphs of linear rankwidth at most k
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, Ojoung; Oum, SangIl (2023), Obstructions for matroids of pathwidth at most k and graphs of linear rankwidth at most k, Journal of Combinatorial Theory. Series B, 160, p. 1535. 10.1016/j.jctb.2022.12.004
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/2109.12291Date
2023Journal name
Journal of Combinatorial Theory. Series BVolume
160Publisher
Elsevier
Pages
1535
Publication identifier
Metadata
Show full item recordAuthor(s)
Kanté, Mamadou MoustaphaLaboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes [LIMOS]
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kwon, Ojoung
Incheon National University
Oum, SangIl
Department of Mathematical Sciences, KAIST
Abstract (EN)
Every minorclosed class of matroids of bounded branchwidth 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 , the list needs to contain only finitely many representable matroids, due to the wellquasiordering of representable matroids of bounded branchwidth under taking matroid minors [J.F. Geelen, A.M.H. Gerards, and G. Whittle (2002)]. But this proof is nonconstructive and does not provide any algorithm for computing these representable excluded minors in general. We consider the class of matroids of pathwidth at most k for fixed k. We prove that for a finite field , every representable excluded minor for the class of matroids of pathwidth at most k has at most elements. We can therefore compute, for any integer k and a fixed finite field , the set of representable excluded minors for the class of matroids of pathwidth k, and this gives as a corollary a polynomialtime algorithm for checking whether the pathwidth of an represented matroid is at most k. We also prove that every excluded pivotminor for the class of graphs having linear rankwidth at most k has at most vertices, which also results in a similar algorithmic consequence for linear rankwidth of graphs.Subjects / Keywords
Pathwidth; Matroid; Linear rankwidth; Forbidden minor; Vertexminor; Pivotminor; GraphRelated items
Showing items related by title and author.

Jeong, Jisu; Kim, Eun Jung; Oum, Sangil (2016) Communication / Conférence

Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, Ojoung; Paul, Christophe (2017) Article accepté pour publication ou publié

Paul, Christophe; Kim, Eun Jung; Kanté, Mamadou Moustapha; Kwon, Ojoung (2015) Communication / Conférence

Jeong, Jisu; Kim, Eun Jung; Oum, SangIl (2021) Article accepté pour publication ou publié

Kim, Eun Jung; Kwon, Ojoung (2018) Communication / Conférence