# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a319492 Showing 1-1 of 1 %I A319492 #10 Sep 28 2018 10:19:18 %S A319492 0,1,25,929,54953,4879508 %N A319492 Number of connected non-3-semi-transitively orientable graphs on n vertices. %C A319492 A graph is k-semi-transitively orientable if it admits an acyclic orientation that avoids shortcuts of length k or less. The notion of a k-semi-transitive orientation refines that of a semi-transitive orientation, which is the case of k equal infinity. For n<9, the number of non-3-semi-transitively orientable graphs is precisely the number of non-semi-transitively orientable graphs, which in turn is the same as the number of non-word-representable graphs. For n=9, there are four 3-semi-transitively orientable graphs which are not semi-transitively orientable. %H A319492 Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, Solving computational problems in the theory of word-representable graphs, arXiv:1808.01215 [math.CO], 2018. %e A319492 The wheel graph W_5 is the only connected graph on 6 vertices that is non-3-semi-transitively orientable. %Y A319492 The first four terms are the same as the terms 5 - 8 in A290814. %K A319492 nonn,more %O A319492 5,3 %A A319492 _Sergey Kitaev_, Sep 20 2018 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE