## 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. 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-colourable 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 K(n,k) is not semi-transitive for any even integers k≥2 and n≥3k and for any odd integers k≥3 and n≥3k+3. On the other hand, for m∈{2k,2k+1}, K(n,k) is semi-transitive. Also, if K(p,q) is not semi-transitive, then K(n,k) is not semi-transitive for any k≥q and [Formula presented]. Moreover, we show computationally that K(8,3) is not semi-transitive, which results in K(n,k) being not semi-transitive for any k≥3 and [Formula presented]. A certain subgraph S of K(8,3) presented by us and K(8,3) itself are the first explicit examples of triangle-free non-semi-transitive graphs, whose existence was established via Erdős’ theorem by Halldórsson, Kitaev and Pyatkin in Halldórsson et al. (2011). Finally, the complement graph K(n,k)¯ of K(n,k) is not semi-transitive if and only if n>2k.

Original language | English |
---|---|

Article number | 111909 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 343 |

Issue number | 8 |

Early online date | 23 Mar 2020 |

DOIs | |

Publication status | Published - 31 Aug 2020 |

## Keywords

- semi-transitive orientations
- Kneser graphs
- acyclic orientation of graphs