Linear Clique-Width for Hereditary Classes of Cographs
Linear Clique-Width for Hereditary Classes of Cographs
复制标题
DOI：
10.1002/jgt.22037
复制
发表时间：
2017-04-01
影响因子：
0.9
通讯作者：
Vatter, Vincent
中科院分区：
文献类型：
--
作者：
Brignall, Robert;Korpelainen, Nicholas;Vatter, Vincent
已知这类上图具有无界的线性上图宽度。证明了一类遗传上图具有有界线性圈宽当且仅当它不包含所有的拟阈值图或它们的补图。证明借用的想法从枚举置换类。(C)2016 Wiley Periodicals，Inc.
The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes. (C) 2016 Wiley Periodicals, Inc.