Viktor Zamaraev (University of Warwick, UK) will give a lecture "Well-quasi-ordering does not imply bounded clique-width (joint work with V. Lozin and I. Razgon)" at the laboratory seminar
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.
Place: 136, Rodionova St., room №401
All are invited!