## Seymour's Second Neighborhood Conjecture

This conjecture has been formulated some time in the 1980's. It is related to
the Caccetta-Haggkvist Conjecture (special case for digraphs in which all in and
out-degrees are n/3). More on the CHC will appear in one or more related
problems later this year.

If G is a digraph and v is a vertex of G, the first neighborhood of v
consists of all out-neighbors of v, and the second neighborhood consists of all
vertices that are not in the first neighborhood but can be reached from v by a
directed path of length 2.

**Conjecture 1:**
Every digraph without loops and digons has a vertex v whose second neighborhood
contains at least as many vertices as its first neighborhood.

The conjecture has been verified for tournaments - Fisher [2] proved it using
algebraic methods. A combinatorial proof was obtained by Havet and Thomasse [3].
Kaneko and Locke [4] proved it for all digraphs with minimum outdegree at most
6. Chen, Shen and Yuster [1] proved that there is a vertex v whose second
neighborhood has at least c times as many vertices as the first one, where c =
0.657298... Besides these results, not much is known.

Bibliography:

[1] Chen, Guantao; Shen, Jian; Yuster, Raphael. Second neighborhood via first
neighborhood in digraphs. Ann. Comb. 7 (2003), 15-20.

[2] Fisher, David C. Squaring a tournament: a proof of Dean's conjecture. J.
Graph Theory 23 (1996), 43-48.

[3] Havet, Frédéric; Thomassé, Stéphan. Median orders of tournaments: a tool
for the second neighborhood problem and Sumner's conjecture. J. Graph Theory 35
(2000), 244-256.

[4] Kaneko, Yoshihiro; Locke, Stephen C. The minimum degree approach for Paul
Seymour's distance 2 conjecture. Proceedings of the Thirty-second Southeastern
International Conference on Combinatorics, Graph Theory and Computing (Baton
Rouge, LA, 2001). Congr. Numer. 148 (2001), 201-206.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: March 15, 2006.