

A319492


Number of connected non3semitransitively orientable graphs on n vertices.


0




OFFSET

5,3


COMMENTS

A graph is ksemitransitively orientable if it admits an acyclic orientation that avoids shortcuts of length k or less. The notion of a ksemitransitive orientation refines that of a semitransitive orientation, which is the case of k equal infinity. For n<9, the number of non3semitransitively orientable graphs is precisely the number of nonsemitransitively orientable graphs, which in turn is the same as the number of nonwordrepresentable graphs. For n=9, there are four 3semitransitively orientable graphs which are not semitransitively orientable.


LINKS

Table of n, a(n) for n=5..10.
Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, Solving computational problems in the theory of wordrepresentable graphs, arXiv:1808.01215 [math.CO], 2018.


EXAMPLE

The wheel graph W_5 is the only connected graph on 6 vertices that is non3semitransitively orientable.


CROSSREFS

The first four terms are the same as the terms 5  8 in A290814.
Sequence in context: A218589 A264006 A218203 * A290814 A218230 A219060
Adjacent sequences: A319489 A319490 A319491 * A319493 A319494 A319495


KEYWORD

nonn,more


AUTHOR

Sergey Kitaev, Sep 20 2018


STATUS

approved



