Clique-Width and the Speed of Hereditary Properties
Clique-Width and the Speed of Hereditary Properties
复制标题
派系宽度和遗传特性的速度
DOI：
--
复制
发表时间：
2009
影响因子：
0.7
通讯作者：
M. Rao
中科院分区：
文献类型：
--
作者：
Peter Allen;V. Lozin;M. Rao
在本文中，我们研究了遗传X类N-Vertex图的数量（也称为X类的速度）与该类别中集团宽度的界限之间的关系。我们表明，如果x的速度比任何c的n！cn都快，则x中图的集合宽度是无绑定的，而如果速度不超过钟数bn，则clique width由一个常数。这两个极端之间的范围更为复杂。该区域包含有界和无界的集团宽度的类别。此外，我们表明，无界集团宽度的图形类别的速度可能比集团宽度的类别较慢。
In this paper, we study the relationship between the number of n-vertex graphs in a hereditary class X, also known as the speed of the class X, and boundedness of the clique-width in this class. We show that if the speed of X is faster than n!cn for any c, then the clique-width of graphs in X is unbounded, while if the speed does not exceed the Bell number Bn, then the clique-width is bounded by a constant. The situation in the range between these two extremes is more complicated. This area contains both classes of bounded and unbounded clique-width. Moreover, we show that classes of graphs of unbounded clique-width may have slower speed than classes where the clique-width is bounded.