On the Clique-Width of Graphs with Few P4's
On the Clique-Width of Graphs with Few P4's
复制标题
关于具有少量 P4 的图的派系宽度
DOI：
10.1142/s0129054199000241
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Udi Rotics
中科院分区：
文献类型：
--
作者：
J. Makowsky;Udi Rotics
Babel和Olariu（1995）引入了一类（q，t）图，其中每一组q个顶点至多有t个不同的诱导P4。图的最大宽度为k的图是由Courcelle，Engelfriet和Rozenberg（1993）引入的，作为可以通过基于使用k个顶点标签的图操作的k-表达式定义的图。在本文中，我们研究了（q，t）图的圈宽度，几乎对所有可能的q和t的组合都是如此。一方面，我们证明了对于q ≥ 7的每个（q，q - 3）图，其cn-width ≤ q，并且可以在线性时间内得到定义它的q-表达式。另一方面，我们证明了当4 ≤ q ≤ 6时的（q，q - 3）图类和当q ≥ 4时的（q，q - 1）图类都不是有界宽度图.
Babel and Olariu (1995) introduced the class of (q, t) graphs in which every set of q vertices has at most t distinct induced P4s. 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 the (q, t) graphs, for almost all possible combinations of q and t. On one hand we show that every (q, q - 3) graph for q ≥ 7, has clique–width ≤ q and a q–expression defining it can be obtained in linear time. On the other hand we show that the class of (q, q - 3) graphs for 4 ≤ q ≤ 6 and the class of (q, q - 1) graphs for q ≥ 4 are not of bounded clique-width.