The strong Seymour vertex conjecture for oriented graphs
The strong Seymour vertex conjecture for oriented graphs
Let be an oriented graph. For a vertex , let and denote its out-neighborhood and second out-neighborhood, respectively. A complete matching from to is a matching consisting of arcs directed from vertices of to vertices of and having every vertex of as a tail. A vertex is a strong Seymour vertex if there is a complete matching from to . 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 into . It is proved in the paper for oriented graphs with minimum out-degree at most and for -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.