On the Clique-Width of Some Perfect Graph Classes
On the Clique-Width of Some Perfect Graph Classes
复制标题
关于一些完美图类的团宽度
DOI：
10.1142/s0129054100000260
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Udi Rotics
中科院分区：
文献类型：
--
作者：
M. Golumbic;Udi Rotics
图的最大宽度为k的图是由Courcelle，Engelfriet和Rozenberg（1993）引入的，作为可以通过基于使用k个顶点标签的图操作的k-表达式定义的图。本文研究了完美图类的圈宽。一方面，我们证明了每一个距离遗传图的宽度不超过3，并且可以在线性时间内得到定义它的3-表达式。另一方面，我们证明了单位区间图类和置换图类都不是有界宽度的。更精确地说，我们证明了对于任意n\in {\mathcal N}$，存在一个单位区间图In和一个有n2个顶点的置换图Hn，每个顶点的cum-width至少为n.这些结果使我们能够看到边界的完美图的层次结构之间的类，其cumber-width是有界的，类的cumber-width是无界的。最后，我们证明了每个n×n正方形网格，n\in {\mathcal N}$，n ≥ 3，都有恰为n+1的宽度。
Graphs of clique–width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In this paper we study the clique–width of perfect graph classes. On one hand, we show that every distance–hereditary graph, has clique–width at most 3, and a 3–expression defining it can be obtained in linear time. On the other hand, we show that the classes of unit interval and permutation graphs are not of bounded clique–width. More precisely, we show that for every $n\in {\mathcal N}$ there is a unit interval graph In and a permutation graph Hn having n2 vertices, each of whose clique–width is at least n. These results allow us to see the border within the hierarchy of perfect graphs between classes whose clique–width is bounded and classes whose clique–width is unbounded. Finally we show that every n×n square grid, $n\in {\mathcal N}$, n ≥ 3, has clique–width exactly n+1.