On semi-transitive orientability of Kneser graphs and their complements

Kitaev, Sergey and Saito, Akira (2020) On semi-transitive orientability of Kneser graphs and their complements. Discrete Mathematics, 343 (8). 111909. ISSN 0012-365X (https://doi.org/10.1016/j.disc.2020.111909)

[thumbnail of Kitaev-Saito-DM-2020-On-semi-transitive-orientability-of-Kneser-graphs]
Preview
 Text. Filename: Kitaev_Saito_DM_2020_On_semi_transitive_orientability_of_Kneser_graphs.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (122kB)| Preview

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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Saito, Akira;
CORE (COnnecting REpositories)