Towards a strengthening of the second neighborhood conjecture

2026/07/20 by Yandong Bai, Binlong Li, Boram Park
#math.CO

paper · pdf

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)|≥ |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.

Related

• Seymour's Second Neighborhood Conjecture for Subsets of Vertices
• The Second Neighborhood Conjecture for Oriented Graphs Missing \C₄, C₄, S₃, chair and co-chair\-Free Graph
• An improved bound on Seymour's second neighborhood conjecture
• The Second Neighborhood Conjecture for Oriented Graphs Missing Combs
• On Seymour's and Sullivan's Second Neighbourhood Conjectures