On Oriented Graphs with Certain Extension Properties

Abstract

Let \(\Gamma\) be an oriented graph. We denote the in-neighborhood and out-neighborhood of a vertex \(v\) in \(\Gamma\) by \(\Gamma^-(v)\) and \(\Gamma^+(v)\), respectively. We say \(\Gamma\) has Property \(A\) if, for each arc \((u,v)\) in \(\Gamma\), each of the graphs induced by \(\Gamma^+(u) \cap \Gamma^+(v)\), \(\Gamma^-(u) \cap \Gamma^-(v)\), \(\Gamma^-(u) \cap \Gamma^+(v)\), and \(\Gamma^+(u) \cap \Gamma^-(v)\) contains a directed cycle. Moreover, \(\Gamma\) has Property B if each arc \((u,v)\) in \(\Gamma\) extends to a \(3\)-path \((x,u), (u,v), (v,w)\), such that \(|\Gamma^+(x) \cap \Gamma^+(u)| \geq 5\) and \(|\Gamma^-(v) \cap \Gamma^-(w)| \geq 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\).