# 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

Text (Kitaev-Saito-DM-2020-On-semi-transitive-orientability-of-Kneser-graphs)
Kitaev_Saito_DM_2020_On_semi_transitive_orientability_of_Kneser_graphs.pdf Accepted Author Manuscript Restricted to Repository staff only until 23 March 2021. License: Download (122kB) | Request a copy from the Strathclyde author |

## 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.

Creators(s): | Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 and Saito, Akira; |
---|---|

Item type: | Article |

ID code: | 71815 |

Keywords: | semi-transitive 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: | 04 Sep 2020 04:47 |

Related URLs: | |

URI: | https://strathprints.strath.ac.uk/id/eprint/71815 |

Export data: |