Seymour's second neighbourhood conjecture

From papers

Let GG be a directed graph. For a vertex vv, write N1+(G,v)N^+_1(G,v) for its out-neighbourhood and N2+(G,v)N^+_2(G,v) for the vertices reachable from vv in two steps but not in one step. An orientation is a directed graph with no directed cycles of length two.

Seymour's second neighbourhood conjecture. Every orientation GG contains at least one vertex vv such that

N2+(G,v)N1+(G,v).|N^+_2(G,v)| \geq |N^+_1(G,v)|.

This is a central open problem about second neighbourhoods in oriented graphs; the paper studies the equality case through Seymour-tight orientations.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Krystal Guo, Ross J. Kang and Gabriëlle Zwaneveld, “Seymour-tight orientations”, arXiv:2603.29626 (2026).

Additional references

20 papers in this index state this conjecture (2006–2026). The statement above is taken from the most recent of them; the others are arXiv:2504.01918, arXiv:2412.20234, arXiv:2406.03635, arXiv:2403.02842, arXiv:2211.06540, arXiv:2010.10790, arXiv:2001.07242, arXiv:1812.01800, arXiv:1808.02247, arXiv:1808.06293, arXiv:1602.08631, arXiv:1509.03282, and 7 more.

Solutions 0

No solutions have been posted yet.