Speaker：Sergey Kitaev（University of Strathclyde，UK）

Time：2022-06-01, 16:00

Location：Tencent Meeting ID：9478414036（Pwd:260172）

Abstract:

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.