Well-quasi-ordering versus clique-width
Well-quasi-ordering versus clique-width
复制标题
良好准排序与团宽度
DOI：
10.1016/j.jctb.2017.09.012
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
V. Zamaraev
中科院分区：
文献类型：
--
作者：
V. Lozin;Igor Razgon;V. Zamaraev
导出子图的良好拟序是否意味着遗传类的团宽度有界？这个问题是由达利高特、拉奥和托马塞提出的[7]。我们否定地回答了这个问题，提出了一类无界团宽度的遗传图类，它是由导出子图关系很好地拟序的。我们还证明了我们类中的图至多有对数团宽度，并且我们类的极小禁止导出子图的个数是无穷的。这些结果导致了一个猜想，放松了上述问题，并导致了一些与良准有序和团宽度相关的公开问题。
Does well-quasi-ordering by induced subgraphs imply bounded clique-width for hereditary classes? This question was asked by Daligault, Rao, and Thomassé [7]. We answer this question negatively by presenting a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered by the induced subgraph relation. We also show that graphs in our class have at most logarithmic clique-width and that the number of minimal forbidden induced subgraphs for our class is infinite. These results lead to a conjecture relaxing the above question and to a number of related open questions connecting well-quasi-ordering and clique-width.
DOI：
10.37236/4074
发表时间：
2015
期刊：
The Electronic Journal of Combinatorics
影响因子：
--
作者：
Atminas A
通讯作者：
Atminas A