Scholarlink

<p>Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes <i>n</i>-vertex graphs of lettericity at most <i>k</i> in time <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(f(k) \cdot n^3\)</EquationSource> </InlineEquation> and show that any minimal graph of lettericity more than <i>k</i> has at most <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(2^{O(k^2\log k)}\)</EquationSource> </InlineEquation> vertices.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月10日

查看全文
  • Bogdan Alecu,
  • Mamadou Moustapha Kanté,
  • Vadim Lozin,
  • Viktor Zamaraev

摘要

Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes n-vertex graphs of lettericity at most k in time \(f(k) \cdot n^3\) and show that any minimal graph of lettericity more than k has at most \(2^{O(k^2\log k)}\) vertices.