when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-39369
URL:

; ;

### Excluded vertex-minors for graphs of linear rank-width at most k.

 pdf-format:

### Abstract

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.

### BibTeX - Entry

@InProceedings{jeong_et_al:LIPIcs:2013:3936,
author =	{Jisu Jeong and O-joung Kwon and Sang-il Oum},
title =	{{Excluded vertex-minors for graphs of linear rank-width at most k.}},
booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages =	{221--232},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-50-7},
ISSN =	{1868-8969},
year =	{2013},
volume =	{20},
editor =	{Natacha Portier and Thomas Wilke},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},