Seymour's second neighbourhood conjecture

About 20 years old · traced to

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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.