Suppose instead that $v_{1}$ is incident with an arc balanced by $u_{3}$.
Since $u_{3}$ is not adjacent to $v_{1}$, it is adjacent to the other
endvertex. Moreover, since $v_{1}$ is adjacent to $v_{2}$ and $v_{4}$, the
other endvertex is also adjacent to $v_{2}$ and $v_{4}$. By the choice of
$u_{3}$, the only vertex that can be adjacent to all of $u_{3},v_{2},v_{4}$ is
$v_{3}$, so the other endvertex is $v_{3}$ and $u_{3}$ is adjacent to $v_{3}$.
Since
$(u_{4},v_{5})\Gamma(v_{2},u_{4})\Gamma(u_{4},v_{3})\Gamma(u_{3},u_{4})\Gamma(v_{4},u_{3})\Gamma(u_{3},v_{1})\Gamma(v_{1},v_{3})$,
the second arc is $(v_{3},v_{1})$. The minimality of $X$ ensures
$\overline{U(X)}$ is Figure 12(vii) and $X$ contains the dotted arcs. ∎

###  4.5 $\overline{U(X)}$ contains a $C_{3}$ and an induced $C_{4}$

######  Lemma 4.16.

Let $X$ be an obstruction which has no cut-vertices. Suppose $\overline{U(X)}$
contains a $C_{3}$ and an induced $C_{4}$. Then $\overline{U(X)}$ contains a
unique $C_{3}$ and a unique induced $C_{4}$, which share two common vertices.
Moreover, each vertex not in any of the cycles is a leaf adjacent to a vertex
on the $C_{3}$ and is incident with an arc.

Proof: By Lemmas 4.4 and 4.5, $\overline{U(X)}$ contains a unique $C_{3}$ and
each vertex not on the $C_{3}$ is adjacent to a vertex in the $C_{3}$. It
follows that each vertex not on the $C_{3}$ is adjacent to exactly one vertex
on the $C_{3}$. We show that if $C$ is an induced $C_{4}$ in $\overline{U(X)}$
then $C$ shares exactly two vertices with the $C_{3}$. Clearly, $C$ share at
most two vertices with the $C_{3}$. The fact that every vertex not on the
$C_{3}$ is adjacent to a vertex in the $C_{3}$ implies that $C$ cannot share
exactly one vertex with the $C_{3}$. If $C$ shares no vertex with the $C_{3}$,
then $C\cup C_{3}$ induces a connected subgraph in $\overline{U(X)}$ with
seven non-cut-vertices, a contradiction to Lemma 4.2.

Denote the unique $C_{3}$ in $\overline{U(X)}$ by $v_{1}v_{2}v_{3}$ and
without loss of generality assume that $v_{2}v_{3}v_{4}v_{5}$ is an induced
$C_{4}$ in the graph. Let $u\notin\\{v_{1},v_{2},\dots,v_{5}\\}$. From the
above we know that $u$ is adjacent to exactly one vertex in the $C_{3}$.
Suppose that $u$ is adjacent to $v_{1}$. Then $u$ cannot be adjacent to both
$v_{4},v_{5}$ as otherwise $uv_{4}v_{5}$ is another $C_{3}$ in
$\overline{U(X)}$, a contradiction. If $u$ is adjacent to one of $v_{4},v_{5}$
then $uv_{1}v_{2}v_{5}v_{4}$ or $uv_{1}v_{3}v_{4}v_{5}$ is an induced $C_{5}$
in $\overline{U(X)}$, which contradicts Lemma 4.7. If $u$ is adjacent to a
vertex $w\notin\\{v_{1},v_{2},\dots,v_{5}\\}$, then $w$ is not adjacent to
$v_{1}$ due to the uniqueness of the $C_{3}$ and so is adjacent to $v_{2}$ or
$v_{3}$. But then $\\{u,w,v_{1},v_{2},\dots,v_{5}\\}$ induces a connected
subgraph of $\overline{U(X)}$ with seven non-cut-vertices, a contradiction to
Lemma 4.2. Hence $u$ is a leaf in $\overline{U(X)}$. Suppose that $u$ is not
adjacent to $v_{1}$. Then it is adjacent to $v_{2}$ or $v_{3}$. By symmetry we
assume $u$ is adjacent to $v_{2}$. It is not adjacent to $v_{5}$ as otherwise
$uv_{2}v_{5}$ is another $C_{3}$ in $\overline{U(X)}$. It is not adjacent to
$v_{4}$ as otherwise $uv_{4}v_{5}v_{2}$ is an induced $C_{4}$ which share just
one vertex (namely, $v_{2}$) with the $C_{3}$. Suppose that $u$ is adjacent to
a vertex $w\notin\\{v_{1},v_{2},\dots,v_{5}\\}$. Then $w$ is not adjacent to
$v_{2}$ due to the uniqueness of the $C_{3}$. It is not adjacent to $v_{1}$
because from the above any such vertex is a leaf. So $w$ is adjacent to
$v_{3}$. But then $\\{u,w,v_{1},v_{2},\dots,v_{5}\\}$ induces a connected
subgraph of $\overline{U(X)}$ with seven non-cut-vertices, a contradiction to
Lemma 4.2. Therefore any vertex $u\notin\\{v_{1},v_{2},\dots,v_{5}\\}$ is a
leaf adjacent to a vertex in the $C_{3}$. It follows that
$v_{2}v_{3}v_{4}v_{5}$ is the unique induced $C_{4}$ in $\overline{U(X)}$. If
such a vertex $u$ is an arc-balancing vertex, then it balances an arc incident
with one of $v_{1},v_{2},v_{3}$, so the other endvertex is adjacent to the
remaining two vertices among $v_{1},v_{2},v_{3}$, contradicting the uniqueness
of the $C_{3}$. Moreover, such a $u$ is not a cut-vertex of $U(X)$ or of
$\overline{U(X)}$. Therefore by Proposition 2.8 $u$ is incident with an arc. ∎

######  Theorem 4.17.

Let $X$ be an obstruction that contains no cut-vertices. Suppose
$\overline{U(X)}$ contains a $C_{3}$ and an induced $C_{4}$. Then
$\overline{U(X)}$ is one of the graphs in Figure 13 and $X$ or its dual
contains the dotted arcs.

$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$$y$$x$$z$ (a) (i)

$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$$y$$x$ (b) (ii)

$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$$y$$z$ (c) (iii)

Figure 13: Obstructions $X$ for which $\overline{U(X)}$ contains a $C_{3}$ and
an induced $C_{4}$.

Proof: By Lemma 4.16, $\overline{U(X)}$ contains a unique $C_{3}$ and a unique
$C_{4}$ sharing two vertices. Denote the $C_{3}$ and the induced $C_{4}$ by
$v_{1}v_{2}v_{3}$ and $v_{2}v_{3}v_{4}v_{5}$ respectively. We also know from
the lemma that every vertex not in any of the cycles is a leaf adjacent to a
vertex in the $C_{3}$ and is incident with an arc. We claim that at least two
vertices of the $C_{3}$ are neighbours of leaves. Indeed, since $U(X)$ does
not contain cut-vertices and $v_{1},v_{2},\dots,v_{5}$ induce a path in
$U(X)$, there must be at least one vertex not on the cycles, which implies at
least one vertex on the $C_{3}$ is adjacent to a leaf. If $v_{2}$ is the only
vertex in the $C_{3}$ adjacent to a leaf. Then $v_{2}$ is adjacent to every
vertex except $v_{4}$ in $\overline{U(X)}$, a contradiction to Lemma 4.1. So
$v_{2}$ cannot be the only vertex in the $C_{3}$ adjacent to a leaf. By
symmetry, $v_{3}$ cannot be the only vertex in the $C_{3}$ adjacent to a leaf.

Suppose $v_{1}$ is the only vertex in the $C_{3}$ adjacent to a leaf. Let $u$
be a leaf of $\overline{U(X)}$ adjacent to $v_{1}$. By Lemma 4.16 $u$ is
incident with an arc. The other endvertex of this arc cannot be another leaf
$v$ as otherwise $uv$ is a balanced edge in $U(X)$, a contradiction. So the
other endvertex of this arc must be among $v_{2},v_{3},v_{4},v_{5}$. Note
first that none of $v_{2},v_{3},v_{4},v_{5}$ is a cut-vertex. If the arc is
between $u$ and $v_{2}$, then $v_{4}$ does not balance this arc as it is
adjacent to neither of the endvertices. So $v_{4}$ either balances or is
incident with the second arc. If $v_{4}$ is incident with the second arc then
$v_{3}$ and $v_{5}$ are arc-balancing vertices, which is not possible. If
$v_{4}$ balances the second arc, then the second arc must be incident with
exactly one of $v_{3},v_{5}$. But then $v_{2}$ is also a vertex adjacent to
exactly one of the endvertices of the second arc, which is again impossible.
This shows there is no arc between $u$ and $v_{2}$. A similar argument shows
that there is no arc between $u$ and any of $v_{3},v_{4},v_{5}$. Therefore at
least two vertices of the $C_{3}$ are neighbours of leaves.

Suppose that all three vertices of the $C_{3}$ are neighbours of leaves. Let
$x,y,z$ be leaves adjacent to $v_{1},v_{2},v_{3}$ respectively. By Lemma 4.16
each of $x,y,z$ is incident with an arc. So there is an arc between two of
$x,y,z$. Suppose there is an arc between $y$ and $z$. By Lemma 4.4, neither of
$v_{4},v_{5}$ can be a cut-vertex so each of them is an arc-balancing vertex
or incident with an arc. At least one of $v_{4},v_{5}$ must be an arc-
balancing vertex because otherwise $x,y,z,v_{4},v_{5}$ would be five vertices
incident with arcs. Without loss of generality, assume $v_{4}$ is an arc-
balancing vertex. Since $v_{4}$ is adjacent to neither of $y,z$, it cannot
balance the arc between $y$ and $z$. Thus $v_{4}$ balances an arc between $x$
and $x_{3}$ or between $x$ and $v_{5}$. This is a contradiction because
$v_{2}$ is another vertex adjacent to exactly one of endvertices of the arc
balanced by $v_{4}$. Thus there is no arc between $y$ and $z$. So there is an
arc between $x$ and $y$ or between $x$ and $z$. By symmetry and taking the
dual of $X$ if necessary we may assume that $(x,z)$ is an arc. Since $v_{1}$
and $v_{3}$ are two vertices adjacent to exactly one of $x,z$, there cannot be
an $(x,z)$-balancing vertex. By Lemma 4.4, $v_{4},v_{5}$ are non-cut-vertices
of $\overline{U(X)}$ so each of them is arc-balancing or incident with an arc
by Proposition 2.8. Clearly, none of them can be an $(x,z)$-balancing vertex.
So either $v_{4}$ balances the arc between $y$ and $v_{5}$ or $v_{5}$ balances
the arc between $y$ and $v_{4}$. The latter case is not possible because
$v_{3}$ is adjacent to $v_{4}$ but not to $y$. Hence there is an arc between
$y$ and $v_{5}$. Since the two arcs of $X$ are opposing and
$(x,z)\Gamma(z,v_{1})\Gamma(v_{2},z)\Gamma(z,y)\Gamma(y,v_{3})\Gamma(v_{4},y)\Gamma(y,v_{5})$,
$(v_{5},y)$ is an arc. The minimality of $X$ ensure that $\overline{U(X)}$ is
the graph in Figure 13(i).

Suppose now that exactly two of $v_{1},v_{2},v_{3}$ are neighbours of leaves.
First consider the case when $v_{1}$ and $v_{2}$ are neighbours of leaves. Let
$x,y$ be leaves adjacent to $v_{1},v_{2}$ respectively. Clearly, $v_{3}$ is
not a cut-vertex. Since $v_{4},v_{5}$ are not the $C_{3}$, by Lemma 4.4 they
are not cut-vertices. Hence, each of $v_{3},v_{4},v_{5}$ is an arc-balancing
vertex or incident with an arc by Proposition 2.8. By Lemma 4.16, $x,y$ are
incident with arcs. So at least one of $v_{3},v_{4},v_{5}$ is an arc-balancing
vertex. If $v_{3}$ is an arc-balancing vertex, then it must balance an arc
incident with $v_{2}$ or $v_{4}$. But then $v_{5}$ is another vertex adjacent
to exactly one endvertex of this arc, a contradiction. Hence $v_{3}$ is not
the arc-balancing vertex. For a similar reason, $v_{5}$ is also not an arc-
balancing vertex. Thus $v_{4}$ is an arc-balancing vertex. It is easy check an
arc balanced by $v_{4}$ cannot be incident with $v_{3}$. So $v_{4}$ balances
an arc incident with $v_{5}$. The other endvertex of this arc cannot be a leaf
adjacent to $v_{1}$. Hence $v_{4}$ balances an arc between $v_{5}$ and a leaf
adjacent to $v_{2}$. Without loss of generality assume it is between $v_{5}$
and $y$. By taking the dual of $X$ if necessary we may assume $(v_{5},y)$ is
an arc. Thus the second arc is between $x$ and $v_{3}$. Since
$(v_{5},y)\Gamma(y,v_{4})\Gamma(v_{4},v_{2})\Gamma(v_{1},v_{4})\Gamma(v_{4},x)\Gamma(x,v_{3})$
and the two arcs of $X$ are opposing, the second arc is $(v_{3},x)$. So
$\overline{U(X)}$ is Figure 13(ii).

The case when $v_{1}$ and $v_{3}$ are neighbours of leaves is symmetric to the
case when $v_{1}$ and $v_{2}$ are cut-vertices. So we now consider the case
where $v_{2}$ and $v_{3}$ are neighbours of leaves. Let $y,z$ be leaves
adjacent to $v_{2},v_{3}$ respectively. By assumption, $v_{1}$ is not a cut-
vertex. Since $v_{4},v_{5}$ are not on the $C_{3}$, they are not cut-vertices
by Lemma 4.4. Thus each of $v_{1},v_{4},v_{5}$ is an arc-balancing vertex or
incident with an arc by Proposition 2.8. It follows that at least one of them
is an arc-balancing vertex. A similar proof as above shows that $v_{4}$
balances an arc between $v_{5}$ and $y$. Without loss of generality, assume
$(v_{5},y)$ is an arc. It is easy to see that $v_{1}$ is not an arc-balancing
vertex so it is incident with an arc. So the second arc is between $v_{1}$ and
$z$. Since
$(v_{5},y)\Gamma(y,v_{4})\Gamma(v_{3},y)\Gamma(y,z)\Gamma(z,v_{2})\Gamma(v_{1},z)$
and the two arcs are opposing, the second arc is $(z,v_{1})$. Hence
$\overline{U(X)}$ is Figure 13(iii). ∎

###  4.6 $\overline{U(X)}$ contains an induced $C_{5}$

######  Lemma 4.18.

Let $X$ be an obstruction which has no cut-vertices. If $C$ is an induced
$C_{5}$ in $\overline{U(X)}$, then the following statements hold:

  1. (a)

$C$ is the unique cycle in $\overline{U(X)}$;

  2. (b)

Each vertex not in $C$ is a leaf adjacent to a vertex in $C$ and incident with
an arc;

  3. (c)

$C$ contains an arc-balancing vertex that is not a cut-vertex of
$\overline{U(X)}$;

  4. (d)

If $v$ is an arc-balancing vertex in $C$, then $v$ balances an arc between a
neighbour of $v$ in $C$ and a leaf.

Proof: Let $C:v_{1}v_{2}v_{3}v_{4}v_{5}$ be an induced $C_{5}$ in
$\overline{U(X)}$. By Lemma 4.3, $C$ is a longest induced cycle in
$\overline{U(X)}$. According to Lemmas 4.6 and 4.7, $\overline{U(X)}$ contains
at most one induced $C_{5}$ but neither $C_{3}$ nor induced $C_{4}$. Thus $C$
is the unique cycle in $\overline{U(X)}$.

Suppose that $u$ is a vertex not in $C$. Then by Lemma 4.4 $u$ is adjacent to
a vertex in $C$. Since $C$ the unique cycle in $\overline{U(X)}$, $u$ is a
leaf and hence not a cut-vertex of $\overline{U(X)}$. Let $v_{i}$ be the
neighbour of $u$. If $u$ is an arc-balancing vertex, then it balances an arc
between $v_{i}$ and some vertex $w$. Since $v_{i}$ is adjacent to both
$v_{i-1},v_{i+1}$ which do not balance the arc between $v_{i}$ and $w$, $w$
must be adjacent to both $v_{i-1},v_{i+1}$. Thus $v_{i}v_{i+1}wv_{i-1}$ is a
$C_{4}$, a contradiction to the fact $C$ is the unique cycle in
$\overline{U(X)}$. Hence $u$ is incident with an arc by Proposition 2.8.

Suppose there are $k$ cut-vertices in $C$. We know from above that each such
vertex is adjacent to a leaf that is incident with an arc. Among the $5-k$
non-cut-vertices in $C$, at most $4-k$ can be incident with arcs because there
are at most four vertices incident with arcs. It follows that $C$ contains at
least one vertex that is not a cut-vertex of $\overline{U(X)}$ and not
incident with an arc. Such a vertex must be an arc-balancing vertex by
Proposition 2.8. Hence $C$ contains an arc-balancing vertex that is not a cut-
vertex of $\overline{U(X)}$. Without loss of generality, assume $v_{1}$ is an
arc-balancing vertex and it balances an arc incident with $v_{2}$. Clearly the
other endvertex cannot be in $C$ so it is a leaf of $\overline{U(X)}$.

Suppose that $v$ a vertex $C$ which balances an arc between $u$ and $w$. If
one of $u,w$ is a leaf neighbour of $v$, then the other endvertex is an
isolated vertex, contradicting the fact that $\overline{U(X)}$ is connected.
So neither of $u,w$ can be a leaf neighbour of $v$. Since $v$ is adjacent to
one of $u,w$, at least one of $u,w$ is in $C$. If the other vertex is also in
$C$, then there is a vertex in $C$ which is not $v$ but is adjacent to exactly
one of $u,w$, a contradiction. Therefore exactly one of $u,w$ is a neighbour
of $v$ in $C$ and the other is a leaf. ∎

######  Theorem 4.19.

Let $X$ be an obstruction that has no cut-vertices. Suppose $\overline{U(X)}$
contains an induced $C_{5}$. Then $\overline{U(X)}$ is one of the graphs in
Figure 14 and $X$ or its dual contains the dotted arcs.

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$$w$$u$ (a) (i)

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$$u$$w$ (b) (ii)

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$$w$$u$$x$ (c) (iii)

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$$u$ (d) (iv)

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$$u$$w$ (e) (v)

$v_{1}$$v_{5}$$v_{4}$$v_{3}$$v_{2}$$w$$u$ (f) (vi)

Figure 14: Obstructions $X$ for which $\overline{U(X)}$ contains an induced
$C_{5}$.

Proof: Let $C:v_{1}v_{2}v_{3}v_{4}v_{5}$ be an induced $C_{5}$ in
$\overline{U(X)}$. By Lemma 4.18, $C$ is the unique cycle in $\overline{U(X)}$
and has a vertex which is an arc-balancing but not a cut-vertex of
$\overline{U(X)}$. Without loss of generality assume $v_{1}$ is such a vertex.
By Lemma 4.18, $v_{1}$ balances an arc between a neighbour of $v_{1}$ in $C$
and a leaf. Without loss of generality, assume $v_{1}$ balances an arc between
$v_{2}$ and $u$ and $(v_{2},u)$ is the arc. Since any vertex except $v_{1}$
that is adjacent to $u$ is also adjacent to $v_{2}$, $u$ is adjacent to
$v_{3}$. Suppose that neither $v_{4}$ nor $v_{5}$ is an arc-balancing vertex.
Then by Proposition 2.8, each of $v_{4},v_{5}$ is a cut-vertex of
$\overline{U(X)}$ or incident with an arc. Since $v_{4},v_{5}$ are adjacent in
$\overline{U(X)}$, there is no arc between them. So one of $v_{4},v_{5}$ is
not incident with an arc and hence must be a cut-vertex of $\overline{U(X)}$.

Suppose $v_{4}$ is a cut-vertex and $v_{5}$ is incident with an arc. By Lemma
4.18(b), there is a leaf $w$ adjacent to $v_{4}$ and incident with an arc.
Hence there is an arc between $v_{5}$ and $w$. Since we have
$(v_{2},u)\Gamma(u,v_{1})\Gamma(v_{1},v_{3})\Gamma(v_{4},v_{1})\Gamma(v_{1},w)\Gamma(w,v_{5})$
and the two arcs are opposing in $X$, the second arc is $(v_{5},w)$. Thus
$\overline{U(X)}$ is Figure 14(i). Suppose instead that $v_{4}$ is incident
with an arc and $v_{5}$ is a cut-vertex. By Lemma 4.18, there is a leaf $w$
adjacent to $v_{5}$ and incident with an arc. Hence there is an arc between
$v_{4}$ and $w$. Since
$(v_{2},u)\Gamma(u,v_{1})\Gamma(v_{1},v_{3})\Gamma(v_{3},v_{5})\Gamma(w,v_{3})\Gamma(v_{4},w)$,
the second arc is $(w,v_{4})$ and $\overline{U(X)}$ is Figure 14(ii). Finally,
suppose both $v_{4}$ and $v_{5}$ are cut-vertices. By Lemma 4.12, there are
leaves $w,x$ adjacent to $v_{4},v_{5}$, respectively, and incident with arcs.
Hence there is an arc between $w$ and $x$. Since we have
$(v_{2},u)\Gamma(u,v_{1})\Gamma(v_{5},u)\Gamma(u,x)\Gamma(x,v_{3})\Gamma(v_{4},x)\Gamma(x,w)$,
the second arc is $(w,x)$. Thus $\overline{U(X)}$ is Figure 14(iii).

Suppose exactly one of $v_{4},v_{5}$ is an arc-balancing vertex. Clearly they
cannot both be arc-balancing vertices because $v_{1}$ is such a vertex and
there are at most two arc-balancing vertices. Consider first the case when
$v_{5}$ is an arc-balancing vertex. Then $v_{5}$ either balances an arc
between $v_{1}$ and a leaf adjacent to $v_{2}$ or an arc between $v_{4}$ and a
leaf adjacent to $v_{3}$. However, the former is not possible, as otherwise
$v_{4}$ is not an arc-balancing vertex and not incident with an arc so it is a
cut-vertex by Proposition 2.8. But then a leaf adjacent to it is not incident
with an arc, a contradiction to Lemma 4.18. So $v_{5}$ balances an arc between
$v_{4}$ and a leaf $w$ adjacent to $v_{3}$. Then we have
$(v_{2},u)\Gamma(u,v_{1})\Gamma(v_{1},v_{3})\Gamma(w,v_{1})\Gamma(v_{5},w)\Gamma(w,v_{4})$.
The second arc is $(v_{4},w)$. When $w=u$, $\overline{U(X)}$ is Figure 14(iv);
otherwise $\overline{U(X)}$ is Figure 14(v).

Consider now the case when $v_{4}$ is an arc-balancing vertex. Then $v_{4}$
either balances an arc between $v_{5}$ and a leaf adjacent to $v_{1}$ or an
arc between $v_{3}$ and a leaf adjacent to $v_{2}$. If $v_{4}$ balances an arc
between $v_{5}$ and a leaf $w$ adjacent to $v_{1}$, then
$(v_{2},u)\Gamma(u,v_{1})\Gamma(v_{1},v_{3})\Gamma(v_{3},w)\Gamma(w,v_{4})\Gamma(v_{5},w)$.
The second arc is $(w,v_{5})$ and $\overline{U(X)}$ is Figure 14(vi). On the
other hand, if $v_{4}$ balances an arc between $v_{3}$ and a leaf adjacent to
$v_{2}$, then $v_{5}$ is not an arc-balancing vertex and not incident with an
arc so it is a cut-vertex by Proposition 2.8. But then a leaf adjacent to it
is not incident with an arc, a contradiction to Lemma 4.18. Hence this is not
possible. ∎

##  5 Conclusion

Theorem 1.1 follows immediately from Corollary 2.2 and Theorems 3.2, 3.4, 3.6,
3.8, 3.10, 3.11, 4.8, 4.11, 4.13, 4.14, 4.15, 4.17, 4.19, and the fact that an
obstruction must be contained in a partially oriented graph which cannot be
completed to a local tournament.

Partially oriented graphs which cannot be completed to local tournaments and
are minimal with respect to only vertex deletions can be derived from Theorem
1.1. Indeed, suppose that $Y$ is such a graph, that is, $Y$ cannot be
completed to a local tournament and for each vertex $v$ of $Y$, $Y-v$ can be
completed to a local tournament. Since $Y$ cannot be completed to a local
tournament, it contains an obstruction. Since $Y$ is minimal with respect to
vertex deletion, $Y$ is either an obstruction described in Theorem 1.1 or is
obtained from an obstruction by orienting some edges.

An oriented graph $D=(V,A)$ is transitive if, for any three vertices $u,v,w\in
V$, $uv\in A$ and $vw\in A$ imply $uw\in A$; it is quasi-transitive if, for
any three vertices $u,v,w\in V$, $uv\in A$ and $vw\in A$ imply $uw\in A$ or
$wu\in A$, cf. [1]. The orientation completion problems for the classes of
transitive and quasi-transitive oriented graphs are polynomial time solvable,
cf. [2]. The underlying graphs of transitive oriented graphs coincide with the
underlying graphs of quasi-transitive oriented graphs, which are known as
comparability graphs, cf. [5, 6, 7]. It remains open problems to find
obstructions for transitive orientation completions and quasi-transitive
orientation completions.

## References

  * [1] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141 - 161.
  * [2] J. Bang-Jensen, J. Huang, and X. Zhu, Completing orientations of partially oriented graphs, J. Graph Theory 87 (2018) 285 - 304.
  * [3] S. Chaplick, R. Fulek, and P. Klavík, Extending partial representations of circle graphs, Lecture Notes in Comput. Sci. 8242 (2013) 131 - 142.
  * [4] S. Chaplick, G. Guśpiel, G. Gutowski, T. Krawczyk, and G. Liotta, The partial visibility representation extension problem, Algorithica 80 (2018) 2286 - 2323.
  * [5] T. Gallai, Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica 18 (1967) 25 - 66.
  * [6] A. Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris 254 (1962) 1370–1371.
  * [7] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.
  * [8] P. Hell and J. Huang, Lexicographic orientation and representation algorithms for comparability graphs, proper circular-arc graphs, and proper interval graphs, J. Graph Theory 20 (1995) 361 - 374.
  * [9] K. Hsu and J. Huang, Obstructions for acyclic local tournament orientation completions, Discrete Math. 2022, in press.
  * [10] J. Huang, On the structure of local tournaments, J. Combin. Theory B (1995) 200 - 221.
  * [11] J. Huang, Lexicographic orientation algorithms for orientation completion problems, Chapter in Classes of Directed Graphs, J. Bang-Jensen and G. Gutin eds., Springer-Verlag, 2018.
  * [12] P. Klaík, Extension properties of graphs and structures, PhD Thesis, Charles University, 2017.
  * [13] P. Klavík, J. Kratochvíl, T. Krawczyk, and B. Walczak, Extending partial representations of function graphs and permutation graphs, Lecture Notes in Comput. Sci. 7501 (2012) 671 - 682.
  * [14] P. Klavík, J. Kratochvíl, Y. Otachi, I. Rutter, T. Saitoh, M. Saumell, and T. Vyskočil, Extending partial representations of proper and unit interval graphs, Algorithmica 77 (2017 1071 - 1104.
  * [15] P. Klavík, J. Kratochvíl, Y. Otachi, and T. Saitoh, Extending partial representations of subclasses of chordal graphs, Theoret. Comput. Sci. 576 (2015) 85 - 101.
  * [16] P. Klavík, J. Kratochvíl, Y. Otachi, T. Saitoh, and T. Vyskočil, Extending partial representations of interval graphs, Algorithmica 78 (2017) 745 - 967.
  * [17] P. Klavík and M. Saumell, Minimal obstructions for partial representations of interval graphs, The Electronic J. Combinatorics 25 (2018) #P4.55.
  * [18] H.E. Robbins, A theorem on graphs with an application to a problem on traffic control, Amer. Math. Mon. 46 (1939) 281 - 283.
  * [19] D.J. Skrien, A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs, J. Graph Theory 6 (1982) 167 - 195.
  * [20] A. Tucker, Structure theorems for some circular-arc graphs, Discrete Math. 7 (1974) 167 - 195.
  * [21] P. Zeman, Extending partial representations of unit circular-arc graphs, arXiv:1706.00928, 2017