The Tree-Width of Clique-Width Bounded Graphs Without Kn, n
The Tree-Width of Clique-Width Bounded Graphs Without Kn, n
复制标题
无 Kn, n 的团宽有界图的树宽
DOI：
10.1007/3-540-40064-8_19
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Egon Wanke
中科院分区：
文献类型：
--
作者：
Frank Gurski;Egon Wanke
我们证明了每一个团宽度为k的图，如果不包含完全二部图Kn，n，对于某n > 1作为子图，树宽度不超过3k(n - 1) - 1。这立即意味着，如果一组有界团宽度的图是一致l-稀疏的、在子图下封闭的、有界度的或平面的，那么它具有有界树宽度。
We proof that every graph of clique-width k which does not contain the complete bipartite graph Kn,n for some n > 1 as a subgraph has tree-width at most 3k(n - 1) - 1. This immediately implies that a set of graphs of bounded clique-width has bounded tree-width if it is uniformly l-sparse, closed under subgraphs, of bounded degree, or planar.