On Oriented Graphs with Certain Extension Properties

Abstract

Let $\mathrm{\Gamma }$ be an oriented graph. We denote the in-neighborhood and out-neighborhood of a vertex $v$ in $\mathrm{\Gamma }$ by ${\mathrm{\Gamma }}^{-}(v)$ and ${\mathrm{\Gamma }}^{+}(v)$, respectively. We say $\mathrm{\Gamma }$ has Property $A$ if, for each arc $(u,v)$ in $\mathrm{\Gamma }$, each of the graphs induced by ${\mathrm{\Gamma }}^{+}(u)\cap {\mathrm{\Gamma }}^{+}(v)$, ${\mathrm{\Gamma }}^{-}(u)\cap {\mathrm{\Gamma }}^{-}(v)$, ${\mathrm{\Gamma }}^{-}(u)\cap {\mathrm{\Gamma }}^{+}(v)$, and ${\mathrm{\Gamma }}^{+}(u)\cap {\mathrm{\Gamma }}^{-}(v)$ contains a directed cycle. Moreover, $\mathrm{\Gamma }$ has Property B if each arc $(u,v)$ in $\mathrm{\Gamma }$ extends to a $3$-path $(x,u),(u,v),(v,w)$, such that $|{\mathrm{\Gamma }}^{+}(x)\cap {\mathrm{\Gamma }}^{+}(u)|\ge 5$ and $|{\mathrm{\Gamma }}^{-}(v)\cap {\mathrm{\Gamma }}^{-}(w)|\ge 5$. We show that the only oriented graphs of order at most $17$, which have both properties $A$ and $B$, are the Tromp graph $T_{16}$ and the graph $T_{16}^{+}$, obtained by duplicating a vertex of $T_{16}$. We apply this result to prove the existence of an oriented planar graph with oriented chromatic number at least $18$.