On semitransitive orientability of trianglefree graphs
Kitaev, Sergey and Pyatkin, Artem (2020) On semitransitive orientability of trianglefree graphs. Discussiones Mathematicae Graph Theory. ISSN 12343099 (In Press)
Preview 
Text (KitaevPyatkinDMGT2021Onsemitransitiveorientabilityoftrianglefree)
Kitaev_Pyatkin_DMGT_2021_On_semi_transitive_orientability_of_triangle_free.pdf Accepted Author Manuscript License: Download (164kB) Preview 
Abstract
An orientation of a graph is semitransitive if it is acyclic, and for any directed path v0→v1→⋯→vk either there is no arc between v0 and vk, or vi→vj is an arc for all 0≤i<j≤k. An undirected graph is semitransitive if it admits a semitransitive orientation. Semitransitive graphs generalize several important classes of graphs and they are precisely the class of wordrepresentable graphs studied extensively in the literature. Determining if a trianglefree graph is semitransitive is an NPhard problem. The existence of nonsemitransitive trianglefree graphs was established via Erdős' theorem by Halldórsson and the authors in 2011. However, no explicit examples of such graphs were known until recent work of the first author and Saito who have shown computationally that a certain subgraph on 16 vertices of the trianglefree Kneser graph K(8,3) is not semitransitive, and have raised the question on the existence of smaller trianglefree nonsemitransitive graphs. In this paper we prove that the smallest trianglefree 4chromatic graph on 11 vertices (the Grötzsch graph) and the smallest trianglefree 4chromatic 4regular graph on 12 vertices (the Chvátal graph) are not semitransitive. Hence, the Grötzsch graph is the smallest trianglefree nonsemitransitive graph. We also prove the existence of semitransitive graphs of girth 4 with chromatic number 4 including a small one (the circulant graph C(13;1,5) on 13 vertices) and dense ones (Toft's graphs). Finally, we show that each 4regular circulant graph (possibly containing triangles) is semitransitive.
ORCID iDs
Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 and Pyatkin, Artem;

Item type: Article ID code: 74710 Dates: DateEvent14 November 2020Published14 November 2020AcceptedKeywords: semitransitive orientation, trianglefree graph, Grotzsch graph, Mycielski graph, Chvatal graph, Toft's graph, circulant graph, Toeplitz graph, Mathematics, Applied Mathematics, Discrete Mathematics and Combinatorics Subjects: Science > Mathematics Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 26 Nov 2020 11:55 Last modified: 27 Jul 2021 12:23 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/74710