The strong Seymour vertex conjecture for oriented graphs

Let DD be an oriented graph. For a vertex xx, let ND+(x)N_D^+(x) and ND++(x)N_D^{++}(x) denote its out-neighborhood and second out-neighborhood, respectively. A complete matching from XX to YY is a matching consisting of arcs directed from vertices of XX to vertices of YY and having every vertex of XX as a tail. A vertex xx is a strong Seymour vertex if there is a complete matching from ND+(x)N_D^+(x) to ND++(x)N_D^{++}(x). Strong Seymour vertex conjecture. Every oriented graph contains a strong Seymour vertex. This would strengthen Seymour's second neighborhood conjecture, since a complete matching injects ND+(x)N_D^+(x) into ND++(x)N_D^{++}(x). It is proved in the paper for oriented graphs with minimum out-degree at most 55 and for 55-anti-transitive oriented graphs, and hence for oriented planar graphs; the general case remains open.

Sources & referencesView supporting material

Primary source

Yandong Bai, Binlong Li and Boram Park, “Towards a strengthening of the second neighborhood conjecture”, arXiv:2607.18047 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.