On semi-transitive orientability of triangle-free graphs

Sergey Kitaev, Artem V. Pyatkin

Research output: Contribution to journalArticlepeer-review

Abstract

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path either there is no arc between and , or is an arc for all . 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ő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 triangle-free Kneser graph 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átal 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 (the circulant graph on 13 vertices) and dense ones (Toft's graphs). Finally, we show that each -regular circulant graph (possibly containing triangles) is semi-transitive.
Original languageEnglish
Number of pages15
JournalDiscussiones Mathematicae Graph Theory
Early online date18 Dec 2020
DOIs
Publication statusE-pub ahead of print - 18 Dec 2020

Keywords

  • semi-transitive orientation
  • triangle-free graph
  • Grotzsch graph
  • Mycielski graph
  • Chvatal graph
  • Toft's graph
  • circulant graph
  • Toeplitz graph

Fingerprint

Dive into the research topics of 'On semi-transitive orientability of triangle-free graphs'. Together they form a unique fingerprint.

Cite this