On semi-transitive orientability of Kneser graphs and their complements

Abstract

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_0\to v_1\to \cdots \to v_k$ either there is no edge between $v_0$ and $v_k$, or $v_i\to v_j$ is an edge for all $0\le i<j\le k$. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs include several important classes of graphs such as 3-colorable graphs, comparability graphs, and circle graphs, and they are precisely the class of word-representable graphs studied extensively in the literature. In this paper, we study semi-transitive orientability of the celebrated Kneser graph $K(n,k)$, which is the graph whose vertices correspond to the $k$-element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. We show that for $n\ge 15k-24$, $K(n,k)$ is not semi-transitive, while for $k\le n\le 2k+1$, $K(n,k)$ is semi-transitive. Also, we show computationally that a subgraph $S$ on 16 vertices and 36 edges of $K(8,3)$, and thus $K(8,3)$ itself on 56 vertices and 280 edges, is non-semi-transitive. $S$ and $K(8,3)$ are the first explicit examples of triangle-free non-semi-transitive graphs, whose existence was established via Erdős' theorem by Halldórsson et al. in 2011. Moreover, we show that the complement graph $\overline{K(n,k)}$ of $K(n,k)$ is semi-transitive if and only if $n\ge 2k$.