editing

approved

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, but orientable graphs which are not semi-transitively orientable graphs.

proposed

editing

editing

proposed

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-rerpesentable representable graphs. For n=9, there are four 3-semi-transitively, but not semi-transitively orientable graphs.

proposed

editing

editing

proposed

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.

Number of connected non-3-semi-transitively orientable graphs on n vertices.

The first four terms are the same as the terms 5 - 8 in A290814.

nonn,more,changed

proposed

editing

editing

proposed

allocated for Sergey KitaevNumber of connected non-3-semi-transitively orientable graphs on n vertices

0, 1, 25, 929, 54953, 4879508

5,3

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-rerpesentable graphs. For n=9, there are four 3-semi-transitively, but not semi-transitively orientable graphs.

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.

Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, <a href="https://arxiv.org/abs/1808.01215">Solving computational problems in the theory of word-representable graphs</a>, arXiv:1808.01215 [math.CO], 2018.

The wheel graph W_5 is the only connected graph on 6 vertices that is non-3-semi-transitively orientable.

The first four terms are the same as the terms 5 - 8 in A290814

allocated

nonn

Sergey Kitaev, Sep 20 2018

approved

editing

allocated for Sergey Kitaev

allocated

approved