Виктор Замараев (Университет Уорвика, Великобритания) выступит с докладом "Well-quasi-ordering does not imply bounded clique-width" (joint work with V. Lozin and I. Razgon) на очередном заседании научного семинара лаборатории ЛАТАС

Well-quasi-ordering is a highly desirable property and frequently discovered concept in mathematics and theoretical computer science. One of the most remarkable recent results in this area is the proof of Wagner’s conjecture stating that the set of all finite graphs is well-quasi-ordered by the minor relation. This is, however, not the case for the induced subgraph relation, since the set of cycles forms an infinite antichain with respect to this relation. On the other hand, the induced subgraph relation may become a well-quasiorder when restricted to graphs in particular classes, such as cographs or k-letter graphs. It is interesting to observe that in both examples we deal with graphs of bounded clique-width, which is another property of great importance in mathematics and computer science. Moreover, the same is true for all available examples of graph classes which are well-quasi-ordered by the induced subgraph relation. This raises an interesting question whether the clique-width is always bounded for graphs in well-quasiordered classes. This question was formally stated as an open problem by Daligault, Rao and Thomass´e. We answer the question negatively by exhibiting a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered by the induced subgraph relation.