论文标题
一个最小的遗传阶层的框架，无限元的图形图
A framework for minimal hereditary classes of graphs of unbounded clique-width
论文作者
论文摘要
我们为遗传图类创建一个框架$ \ MATHCAL {g}^δ$构建在二维顶点网格和边缘集的框架上，由三重$δ= \Δ= \ {α，β，β，γ，γ\} $定义了连续列之间的边缘之间，并在不连续列之间进行了键之间的键（均为债券之间）（均为债券）（均为债券）（均为债券）（均为债券）和（均为债券）。该框架捕获了所有以前证明的无限范围宽度图和许多新框架的最小遗传类别，尽管我们没有声称这包括所有这些类别。 我们表明，当且仅当某个参数$ \ MATHCAL {n}^δ$无绑定时，当$ \ MATHCAL {g}^δ$具有无界的clique-width时。我们进一步表明，如果另一个参数$ \ nathcal {m}^β$有界，并且$δ$ $δ$，则$ \ MATHCAL {G}^δ$是无限制的Clique fidth的最小值（实际上是最小的无限线性三分位数），并且$δ$也具有重复的特征。这两个参数$ \ MATHCAL {N}^δ$和$ \ Mathcal {M}^β$都是三重$δ=（α，β，γ）$的属性，并测量某些辅助图中不同社区的数量。 在我们的整个工作中，我们将新方法介绍了集团宽度的研究，包括在与无限制相关的参数中使用拉姆齐理论，以及对无界群体宽度最小类别的亚类的显式（线性）分类宽度表达式。
We create a framework for hereditary graph classes $\mathcal{G}^δ$ built on a two-dimensional grid of vertices and edge sets defined by a triple $δ=\{α,β,γ\}$ of objects that define edges between consecutive columns, edges between non-consecutive columns (called bonds), and edges within columns. This framework captures all previously proven minimal hereditary classes of graph of unbounded clique-width, and many new ones, although we do not claim this includes all such classes. We show that a graph class $\mathcal{G}^δ$ has unbounded clique-width if and only if a certain parameter $\mathcal{N}^δ$ is unbounded. We further show that $\mathcal{G}^δ$ is minimal of unbounded clique-width (and, indeed, minimal of unbounded linear clique-width) if another parameter $\mathcal{M}^β$ is bounded, and also $δ$ has defined recurrence characteristics. Both the parameters $\mathcal{N}^δ$ and $\mathcal{M}^β$ are properties of a triple $δ=(α,β,γ)$, and measure the number of distinct neighbourhoods in certain auxiliary graphs. Throughout our work, we introduce new methods to the study of clique-width, including the use of Ramsey theory in arguments related to unboundedness, and explicit (linear) clique-width expressions for subclasses of minimal classes of unbounded clique-width.
