An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_0rightarrow v_1rightarrow cdotsrightarrow v_k$ either there is no edge between $v_0$ and $v_k$, or $v_irightarrow v_j$ is an edge for all $0leq i<jleq 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 $ngeq 15k-24$, $K(n,k)$ is not semi-transitive, while for $kleq nleq 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 ErdH{o}s theorem by Halld{o}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 $ngeq 2k$.
تحميل البحث