On semitransitive orientability of Kneser graphs and their complements
Kitaev, Sergey and Saito, Akira (2020) On semitransitive orientability of Kneser graphs and their complements. Discrete Mathematics, 343 (8). 111909. ISSN 0012365X (https://doi.org/10.1016/j.disc.2020.111909)
Preview 
Text.
Filename: Kitaev_Saito_DM_2020_On_semi_transitive_orientability_of_Kneser_graphs.pdf
Accepted Author Manuscript License: Download (122kB) Preview 
Abstract
An orientation of a graph is semitransitive 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 semitransitive if it admits a semitransitive orientation. Semitransitive graphs include several important classes of graphs such as 3colourable graphs, comparability graphs, and circle graphs, and they are precisely the class of wordrepresentable graphs studied extensively in the literature. In this paper, we study semitransitive orientability of the celebrated Kneser graph K(n,k), which is the graph whose vertices correspond to the kelement 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 semitransitive 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 semitransitive. Also, if K(p,q) is not semitransitive, then K(n,k) is not semitransitive for any k≥q and [Formula presented]. Moreover, we show computationally that K(8,3) is not semitransitive, which results in K(n,k) being not semitransitive 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 trianglefree nonsemitransitive 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 semitransitive if and only if n>2k.
ORCID iDs
Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 and Saito, Akira;

Item type: Article ID code: 71815 Dates: DateEvent31 August 2020Published23 March 2020Published Online10 March 2020AcceptedKeywords: semitransitive orientations, Kneser graphs, acyclic orientation of graphs, Mathematics, Discrete Mathematics and Combinatorics, Theoretical Computer Science Subjects: Science > Mathematics Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 19 Mar 2020 12:54 Last modified: 22 Mar 2023 02:20 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/71815