2026-07-20T14:48:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3936 2024-03-06T10:34:40Z ddc:004 open_access

Excluded vertex-minors for graphs of linear rank-width at most k. Jeong, Jisu Kwon, O-joung Oum, Sang-il rank-width linear rank-width vertex-minor well-quasi-ordering Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each k, there is a finite set \mathcal{O}_k of graphs such that a graph G has linear rank-width at most k if and only if no vertex-minor of G is isomorphic to a graph in \mathcal{O}_k. However, no attempts have been made to bound the number of graphs in \mathcal{O}_k for k >= 2. We construct, for each k, 2^{\Omega(3^k)} pairwise locally non-equivalent graphs that are excluded vertex-minors for graphs of linear rank-width at most k. Therefore the number of graphs in \mathcal{O}_k is at least double exponential. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jisu Jeong and O-joung Kwon and Sang-il Oum 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.221 urn:nbn:de:0030-drops-39369 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.221 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode