Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As far as I know, it is still open. Here are some of related results (Probably you know all of them):
- Chen-Shen-Yuster proved that for any digraph $D$, there exists a vertex $v$ such that $|N^{++}(v)|\geq\gamma|N^+(v)|$, where $\gamma=0.67815.$. See "Second neighborhood via first neighborhood in digraphs", Ann. Comb. 7 (2003), no. 1, 15–20. (Recall Seymour's second neighborhood conjecture asserts that $|N^{++}(v)|\geq|N^+(v)|$ for some $v$.)
- Fisher proved that Seymour's second neighborhood conjecture is true for tournament $D$, that is, the underlying graph of $D$ is a complete graph. See "Squaring a tournament: a proof of Dean's conjecture", J. Graph Theory 23 (1996), no. 1, 43–48.
- Ghazal proved that Seymour's second neighborhood conjecture is true for tournaments missing a generalized star. See "Seymour's second neighborhood conjecture for tournaments missing a generalized star", J. Graph Theory 71 (2012), no. 1, 89–94.
