On semi-transitive orientability of triangle-free graphs

Sergey Kitaev, Artem Pyatkin

Published 2020-03-13Version 1

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_0\rightarrow v_1\rightarrow \cdots\rightarrow v_k$ either there is no edge between $v_0$ and $v_k$, or $v_i\rightarrow v_j$ is an edge for all $0\leq i<j\leq k$. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs generalize several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. Determining if a triangle-free graph is semi-transitive is an NP-hard problem. The existence of non-semi-transitive triangle-free graphs was established via Erd\H{o}s' theorem by Halld\'{o}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 triangle-free Kneser graph $K(8,3)$ is not semi-transitive, and have raised the question on the existence of smaller triangle-free non-semi-transitive graphs. In this paper we prove that the smallest triangle-free 4-chromatic graph on 11 vertices (the Gr\"otzsch graph) and the smallest triangle-free 4-chromatic 4-regular graph on 12 vertices (the Chv\'atal graph) are not semi-transitive. Hence, the Gr\"otzsch graph is the smallest triangle-free non-semi-transitive graph. We also prove the existence of semi-transitive graphs of girth 4 with chromatic number 4 including a small one (on 13 vertices) and dense ones (Toft's graphs).