Towards a strengthening of the second neighborhood conjecture

Abstract

A longstanding conjecture of Seymour, called Seymour's second neighborhood conjecture, states that every oriented graph $D$ contains a vertex $x$ with $|N_D^{++}(x)|\ge |N_D^{+}(x)|$. The conjecture was verified in a few special classes of oriented graphs, and it remains open for general oriented graphs. We study a stronger property, asking for a vertex $x$ such that there exists a complete matching from $N_D^{+}(x)$ to $N_D^{++}(x)$. We prove that this stronger version holds for every oriented graph with minimum out-degree at most $5$, and also for every $5$-anti-transitive oriented graph. This implies that every oriented planar graph satisfies the stronger version.