{
  "id": "2003.06204",
  "version": "v1",
  "published": "2020-03-13T11:18:06.000Z",
  "updated": "2020-03-13T11:18:06.000Z",
  "title": "On semi-transitive orientability of triangle-free graphs",
  "authors": [
    "Sergey Kitaev",
    "Artem Pyatkin"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-13T11:18:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "triangle-free graph",
      "semi-transitive orientability",
      "smallest triangle-free non-semi-transitive graph",
      "triangle-free kneser graph",
      "smaller triangle-free non-semi-transitive graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}