← All problems

Sullivan's second neighbourhood conjecture

2 years old · documented by

Let GG be an oriented graph. For a vertex vv, let N2+(v)N^+_2(v) be its second out-neighbourhood and let N1−(v)N^-_1(v) be its in-neighbourhood.

Sullivan's conjecture. Every oriented graph contains at least one vertex vv such that

∣N2+(v)∣≥∣N1−(v)∣.|N^+_2(v)| \geq |N^-_1(v)|.

Sullivan proposed this variation of Seymour's conjecture in a survey on the Caccetta–Häggkvist conjecture. The paper constructs special putative counterexamples and studies highly symmetric cases, but the conjecture remains open.

References

3 papers in this index state this conjecture (2023–2026). The statement above is taken from the most recent of them; the others are arXiv:2403.02842, arXiv:2306.03493.

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

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.