Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Jeong, Jisu; Kwon, O-joung; Oum, Sang-il http://www.dagstuhl.de/lipics License
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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3936},
  URN =		{urn:nbn:de:0030-drops-39369},
  doi =		{10.4230/LIPIcs.STACS.2013.221},
  annote =	{Keywords: rank-width, linear rank-width, vertex-minor,  well-quasi-ordering}
}

Keywords: rank-width, linear rank-width, vertex-minor, well-quasi-ordering
Seminar: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue date: 2013
Date of publication: 2013


DROPS-Home | Fulltext Search | Imprint Published by LZI