On semi-transitive orientability of Kneser graphs and their complements

Sergey Kitaev, Akira Saito

Research output: Contribution to journalArticle

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 languageEnglish
Article number111909
Number of pages7
JournalDiscrete Mathematics
Volume343
Issue number8
Early online date23 Mar 2020
DOIs
Publication statusE-pub ahead of print - 23 Mar 2020

    Fingerprint

Keywords

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

Cite this