Topics Covered

TOPICS TO BE COVERED IN THIS SCHOOL

Some Aspects of Semi-Transitively Orientable Graphs

By Professor. Sergey Kitaev, University of Strathclyde Glasgow

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path

$$ v_0~ \overrightarrow{} ~v_1~ \overrightarrow{}~ ...~ \overrightarrow{} ~ v_k $$

cid:3248131967*[email protected]

either there is no edge between

$$ v_0~and~v_k $$

cid:3248131967*[email protected]

$$ v_i~\overrightarrow{}~v_i $$

cid:3248131967*[email protected]

is an edge for all

$$ 0~ \le~i~<~j ~\le ~k $$

cid:3248131967*[email protected]

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 lecture, I will go over some basics of the theory of semi-transitive graphs, and will introduce several open problems/research directions.

Some Aspects of Dominations in Graphs

By Professor Michael Henning, University of Johannesburg