3
$\begingroup$

Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.

$\endgroup$
4
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.