Selected open problems on semi-transitive graphs

：Sergey Kitaev（英国思克莱德大学）
：2022-06-01 16:00
：腾讯会议ID：9478414036（密码：260172）

报告人：Sergey Kitaev（英国思克莱德大学）

时  间：6月1日下午16:00

地  点：腾讯会议ID：9478414036（密码：260172）

内容摘要:

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v_0 -> v_1 -> … -> v_k either there is no edge between v_0 and v_k, or v_i -> v_j is an edge for all 0 <= i < j <=k. Semi-transitive graphs generalize several important classes of graphs (such as 3-colorable, subcubic, circle and comparability graphs) and they are precisely the class of word-representable graphs studied extensively in the literature. Not all graphs are semi-transitive, and recognizing semi-transitivity is an NP-complete problem. In this talk, I will go over some basics of the theory of semi-transitive graphs, and will discuss several open problems along with known results related to them.

个人简介：

Sergey Kitaev，英国思克莱德大学理学院副院长、教授。2003年博士毕业于瑞典哥德堡大学。主要研究组合计数问题，完成了置换与词和图的两本著作，在J. Combin. Theory Ser. A，Adv in Appl. Math., European J. Combin.等杂志上发表多篇文章。先后主持过冰岛和英国国家基金委的项目，并多次被邀请在重要组合数学会议上做大会报告。

 

联系人：靳宇