Document Open Access Logo

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

Authors Jisu Jeong, O-joung Kwon, Sang-il Oum

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2013.221.pdf
  • Filesize: 0.65 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • rank-width
  • linear rank-width
  • vertex-minor
  • well-quasi-ordering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Jisu Jeong, O-joung Kwon, and Sang-il Oum. Excluded vertex-minors for graphs of linear rank-width at most k.. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 221-232, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013) https://doi.org/10.4230/LIPIcs.STACS.2013.221

Author Details

Jisu Jeong
O-joung Kwon
Sang-il Oum
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact