Split Permutation Graphs
Split Permutation Graphs
复制标题
分割排列图
DOI：
10.1007/s00373-013-1290-3
复制
发表时间：
2013
影响因子：
0.7
通讯作者：
Korpelainen N
中科院分区：
文献类型：
--
作者：
Korpelainen N
分裂置换图是分裂图和置换图这两类重要的置换图的交集。它还包含一个重要的子类，即阈值图。这类门限图具有许多良好的性质。特别地，这些图具有有界团宽度，并且它们是由导出子图关系很好地拟序的。众所周知，这两个性质都不能扩展到分裂图或置换图。本文研究了这两个性质对分裂置换图的可扩性问题。关于这两个性质，我们都否定地回答了这个问题。此外，我们猜想，关于这两者，分裂置换图构成了一个临界类。
The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.
登录
查看更多内容
关于具有少量 P4 的图的派系宽度
DOI：
10.1142/s0129054199000241
发表时间：
1999
期刊：
Int. J. Found. Comput. Sci.
影响因子：
--
作者：
J. Makowsky;Udi Rotics
通讯作者：
Udi Rotics
影响因子：
0.8
作者：
Petkovsek, M
通讯作者：
Petkovsek, M
关于一些完美图类的团宽度
DOI：
10.1142/s0129054100000260
发表时间：
2000
期刊：
Int. J. Found. Comput. Sci.
影响因子：
--
作者：
M. Golumbic;Udi Rotics
通讯作者：
Udi Rotics
可数图的团宽度：紧凑性属性
DOI：
--
发表时间：
2000
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
B. Courcelle
通讯作者：
B. Courcelle
Dilworth 2 号的分割图
DOI：
10.1016/0012-365x(85)90040-8
发表时间：
1985
期刊：
Discret. Math.
影响因子：
--
作者：
C. Benzaken;P. Hammer;D. Werra
通讯作者：
D. Werra