On semi-transitive orientability of split graphs

A directed graph is semi-transitive if and only if it is acyclic and for any directed path u(1)-> u(2)->& ctdot;-> u(t), t >= 2, either there is no edge from u1 to ut or all edges u(i)-> u(j) exist for 1 <= i<= t. Recognizing semi-transitive orientability of a graph is an NP-complete problem. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Semi-transitive orientability of split graphs was recently studied in a series of papers in the literature. The main result in this paper is proving that recognition of semi-transitive orientability of split graphs can be done in a polynomial time.

Automated summary

This article discusses the properties of semi-transitive directed graphs and split graphs, pointing out that recognizing the semi-transitive orientability is an NP-complete problem. It also proves that the recognition of semi-transitive orientability of split graphs can be done in polynomial time.