An orientation of a graph is semi-transitive if it is acyclic, and for any directed path _{0} → _{1} → → _{k}_{0} and _{k}_{i}_{j}

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

#### Keywords

- semi-transitive orientation
- triangle-free graph
- Grötzsch graph
- Mycielski graph
- Chvátal graph
- Toft’s graph
- circulant graph
- Toeplitz graph

#### MSC 2010

- 05C62

New Results on Type 2 Snarks ^{1}Relationship among B1-EPG, VPT and EPT Graphs Classes Relaxed DP-Coloring and another Generalization of DP-Coloring on Planar Graphs without 4-Cycles and 7-Cycles Chorded k -Pancyclic and Weaklyk -Pancyclic GraphsA Characterization of Internally 4-Connected {P _{10}− {V_{1}, V_{2}}}-Minor-Free GraphsOn s -Hamiltonian-Connected Line GraphsEnumerating the Digitally Convex Sets of Powers of Cycles and Cartesian Products of Paths and Complete Graphs New Bounds on Domination and Independence in Graphs ^{1}Two Sufficient Conditions for Component Factors in Graphs The Turán Number of Spanning Star Forests Well-Covered Token Graphs On the Metric Dimensions for Sets of Vertices Beta Invariant and Chromatic Uniqueness of Wheels Hop Domination in Chordal Bipartite Graphs Cubic Graphs Having Only k -Cycles in Each 2-FactorMinimizing the Number of Complete Bipartite Graphs in a K -Saturated Graph_{s}Some Results on Path-Factor Critical Avoidable Graphs On a Graph Labelling Conjecture Involving Coloured Labels Double Total Dominator Chromatic Number of Graphs Graph Grabbing Game on Graphs with Forbidden Subgraphs Forbidden Subgraphs for Existences of (Connected) 2-Factors of a Graph On the Broadcast Independence Number of Locally Uniform 2-Lobsters The Hilton-Spencer Cycle Theorems Via Katona’s Shadow Intersection Theorem Cycles of Many Lengths in Balanced Bipartite Digraphs on Dominating and Dominated Degree Conditions Extending Potočnik and Šajna’s Conditions on the Existence of Vertex-Transitive Self-Complementary k -HypergraphsOn the Sizes of ( k, l )-Edge-Maximalr -Uniform HypergraphsA Note on the Upper Bounds on the Size of Bipartite and Tripartite 1-Embeddable Graphs on Surfaces Spanning Trees with a Bounded Number of Branch Vertices in a K _{1,4}-Free GraphCoalition Graphs of Paths, Cycles, and Trees A Characterization of Uniquely Representable Graphs Panchromatic Patterns By Paths On P _{5}-Free Locally Split GraphsBounds on the Total Double Roman Domination Number of Graphs On the ρ -Subdivision Number of GraphsScaffold for the Polyhedral Embedding of Cubic Graphs The Linear Arboricity of Graphs with Low Treewidth Vertex-Edge Domination in Interval and Bipartite Permutation Graphs Domination Game: Effect of Edge Contraction and Edge Subdivision The Decycling Number of a Planar Graph Covered By K _{4}-SubgraphsOn Q -Connected Chordal Graphs with Minimum Number of Spanning TreesDegree Sum Condition for Vertex-Disjoint 5-Cycles Strong and Weak Perfect Digraph Theorems for Perfect, α-Perfect and Strictly Perfect Digraphs L (2, 1)-Labeling of the Iterated Mycielski Graphs of Graphs and Some Problems Related to Matching ProblemsAbout an Extremal Problem of Bigraphic Pairs with a Realization Containing K _{s,t}^{1}On the Equality of Domination Number and 2-Domination Number Optimal Error-Detecting Open-Locating-Dominating Set on the Infinite Triangular Grid The Achromatic Number of the Cartesian Product of K _{6}andK _{q}The Graph Grabbing Game on Blow-ups of Trees and Cycles A Note on Forcing 3-Repetitions in Degree Sequences Linear Arboricity of 1-Planar Graphs Vertex Partitioning of Graphs Into Odd Induced Subgraphs On the Ramsey Numbers of Non-Star Trees Versus Connected Graphs of Order Six Daisy Hamming Graphs Edge Degree Conditions for Dominating and Spanning Closed Trails Strengthening Some Complexity Results on Toughness of Graphs Unique Minimum Semipaired Dominating Sets in Trees Extremal Graphs for Even Linear Forests in Bipartite Graphs ℓ -Coveringk -Hypergraphs are Quasi-EulerianZero and Total Forcing Dense Graphs On Conditional Connectivity of the Cartesian Product of Cycles The Walks and CDC of Graphs with the Same Main Eigenspace Burnside Chromatic Polynomials of Group-Invariant Graphs Total and Paired Domination Stability in Prisms Generalized Turán Problems for Small Graphs The Achromatic Number of K _{6}□K Equals 2_{q}q + 3 Ifq ≥ 41 is OddTotal 2-Domination Number in Digraphs and Its Dual Parameter Metric Dimension and Diameter in Bipartite Graphs A Decomposition for Digraphs with Minimum Outdegree 3 Having No Vertex Disjoint Cycles of Different Lengths On Semi-Transitive Orientability of Triangle-Free Graphs Countable Graphs Are Majority 3-Choosable Identifying Codes in the Direct Product of a Path and a Complete Graph Determining Number and Cost of Generalized Mycielskian Graphs Set-Sequential Labelings of Odd Trees Lower Boundary Independent Broadcasts in Trees Improved Bounds for Some Facially Constrained Colorings Minimal Graphs with Disjoint Dominating and Total Dominating Sets Equimatchable Bipartite Graphs The Threshold Dimension and Irreducible Graphs Edge Intersection Hypergraphs More Tales of Hoffman: Bounds for the Vector Chromatic Number of a Graph On Distance Magic Labelings of Hamming Graphs and Folded Hypercubes An Upper Bound on the Chromatic Number of 2-Planar Graphs The Existence of Path-Factor Covered Graphs On Subgraphs with Prescribed Eccentricities Domination Parameters of the Unitary Cayley Graph of / n Double Roman and Double Italian Domination An Improved Bound on the Chromatic Number of the Pancake Graphs Efficient ( j ,k )-Dominating FunctionsElimination Properties for Minimal Dominating Sets of Graphs Choosability with Separation of Cycles and Outerplanar Graphs The Neighbor-Locating-Chromatic Number of Trees and Unicyclic Graphs Edge-Maximal Graphs with Cutwidth at Most Three The Petersen and Heawood Graphs Make Up Graphical Twins Via Induced Matchings A Note About Monochromatic Components in Graphs of Large Minimum Degree