An improved bound on Seymour's second neighborhood conjecture
classification
🧮 math.CO
keywords
secondconjecturefirstneighborhoodout-neighborhoodseymourbestbound
read the original abstract
Seymour's celebrated second neighborhood conjecture, now more than thirty years old, states that in every oriented digraph, there is a vertex $u$ such that the size of its second out-neighborhood $N^{++}(u)$ is at least as large as that of its first out-neighborhood $N^+(u)$. In this paper, we prove the existence of $u$ for which $|N^{++}(u)| \ge 0.715538 |N^+(u)|$. This result provides the first improvement to the best known constant factor in over two decades.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7
Authors prove Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree 7 via local reductions followed by computer-assisted infeasibility checks on finite obstructions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.